[Bug tree-optimization/109462] New: [13 Regression] Possible miscompilation of clang LocalizationChecker since r13-1938

[Bug tree-optimization/109462] New: [13 Regression] Possible miscompilation of clang LocalizationChecker since r13-1938

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109462

            Bug ID: 109462
           Summary: [13 Regression] Possible miscompilation of clang
                    LocalizationChecker since r13-1938
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: jakub at gcc dot gnu.org
  Target Milestone: ---

Created attachment 54823
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=54823&action=edit
LocalizationChecker.ii.xz

As mentioned in (but not reported to us) in
https://github.com/llvm/llvm-project/issues/59227
// clang -cc1 test.m -analyze -setup-static-analyzer
-analyzer-checker=optin.osx.cocoa.localizability.EmptyLocalizationContextChecker
#define nil ((id)0)
#define NSLocalizedString(key, comment) [[NSBundle mainBundle]
localizedStringForKey:(key) value:@"" table:nil]
struct CGPoint { double x; double y; };
typedef struct CGPoint CGPoint;
@interface NSObject
+ (id)alloc;
- (id)init;
@end
@class NSDictionary;
@interface NSString : NSObject
- (void)drawAtPoint:(CGPoint)point withAttributes:(NSDictionary *)attrs;
+ (instancetype)localizedStringWithFormat:(NSString *)format, ...;
@end
@interface NSBundle : NSObject
+ (NSBundle *)mainBundle;
- (NSString *)localizedStringForKey:(NSString *)key
                              value:(NSString *)value
                              table:(NSString *)tableName;
@end
@interface LocalizationTestSuite : NSObject
@end
@implementation LocalizationTestSuite
- (void)testNilLocalizationContext {
  NSString *string = NSLocalizedString(@"LocalizedString", nil);
}
@end
reports an (expected) warning when
clang/lib/StaticAnalyzer/Checkers/LocalizationChecker.cpp is compiled with
r13-1937 and earlier, while
when compiled with r13-1938 and later the warning is not emitted.
The r13-1938 changes cause differences in
_ZNK5clang13SourceManager16getDecomposedLocENS_14SourceLocationE
and
_ZN12_GLOBAL__N_131EmptyLocalizationContextChecker13MethodCrawler20VisitObjCMessageExprEPKN5clang15ObjCMessageExprE
functions and it is the latter that matters for whether the warning is reported
or not (proved by hand-combining assembly
from the 2 revisions, everything from r13-1937 but the
_ZN12_GLOBAL__N_131EmptyLocalizationContextChecker13MethodCrawler20VisitObjCMessageExprEPKN5clang15ObjCMessageExprE
function from r13-1938 doesn't report the warning, everything from r13-1938 but
that function from r13-1937 does.
First difference in both functions appears in the dom2 dumps.

Flags used to compile were -fPIC -fno-semantic-interposition
-fvisibility-inlines-hidden -ffunction-sections -fdata-sections -fno-common
-fno-strict-aliasing -O3 -fno-exceptions -funwind-tables -fno-rtti -std=c++17
LocalizationChecker.ii

[Bug tree-optimization/109462] [13 Regression] Possible miscompilation of clang LocalizationChecker since r13-1938

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109462

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |13.0
                 CC|                            |aldyh at gcc dot gnu.org,
                   |                            |amacleod at redhat dot com

[Bug tree-optimization/109462] [13 Regression] Possible miscompilation of clang LocalizationChecker since r13-1938

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109462

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |wrong-code
           Severity|normal                      |critical

[Bug tree-optimization/109462] [13 Regression] Possible miscompilation of clang LocalizationChecker since r13-1938

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109462

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
When stepping through the function in the debugger, the difference appears in
the
  Token I;
  Token Result;
  int p_count = 0;
  while (!TheLexer.LexFromRawLexer(I)) {
    if (I.getKind() == tok::l_paren)
      ++p_count;
    if (I.getKind() == tok::r_paren) {
      if (p_count == 1)
        break;
      --p_count;
    }
    Result = I;
  }

loop followed by:
  if (isAnyIdentifier(Result.getKind())) {
I see 7 iterations of the loop where the 2nd increments p_count to 1
and then in the expected behavior we reach the isAnyIdentifier expression in
the if statement after the loop.
In the non-expected behavior also 7 iterations, but in the last one I see:
1157        if (I.getKind() == tok::l_paren)
(gdb) 
1159        if (I.getKind() == tok::r_paren) {
(gdb) 
1160          if (p_count == 1)
(gdb) n
1184    }
(gdb) n
(anonymous
namespace)::EmptyLocalizationContextChecker::MethodCrawler::VisitChildren
(this=0x7fffffffb830, S=<optimized out>) at
/usr/src/llvm-project/clang/lib/StaticAnalyzer/Checkers/LocalizationChecker.cpp:1060
1060          for (const Stmt *Child : S->children()) {
so basically it didn't break but did return or so.
The expected behavior under debugger was:
1157        if (I.getKind() == tok::l_paren)
(gdb) 
1159        if (I.getKind() == tok::r_paren) {
(gdb) 
1160          if (p_count == 1)
(gdb) 
1167      if (isAnyIdentifier(Result.getKind())) {
so, I think the 2nd iteration has I.getKind() == tok::l_paren and the 7th ==
tok::r_paren and no other iteration has those kinds.

[Bug tree-optimization/109462] [13 Regression] Possible miscompilation of clang LocalizationChecker since r13-1938

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109462

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Under debugger (trunk) what I see is that the block_result.intersect
(equiv_range)
in the code added by r13-1938 is only true in the VisitObjCMessageExpr function
twice, each time on the
  # Result$16_552 = PHI <Result$16_670(144), Result$16_453(D)(138)>
SSA_NAME, on the
<bb 120> [local count: 251634481]:
if (p_count_732 == 1)
  goto <bb 124>; [5.50%]
else
  goto <bb 121>; [94.50%]
block (i.e. one guarded with _143 == 22 condition),
which has originally VARYING block_result, but equiv_name is strangely
_143 set by
  _143 = I.Kind;
earlier.  Obviously the range for _143 in that bb is [22, 22], that is correct,
what isn't correct is that it would be equivalent to Result$16_552.
The IL of the loop is:

  <bb 139> [local count: 740101405]:
  _143 = I.Kind;
  if (_143 == 21)
    goto <bb 140>; [34.00%]
  else
    goto <bb 141>; [66.00%]

  <bb 140> [local count: 251634481]:
  # RANGE [irange] int [-2147483647, +INF]
  p_count_87 = p_count_732 + 1;
  goto <bb 144>; [100.00%]

  <bb 141> [local count: 488466924]:
  if (_143 == 22)
    goto <bb 142>; [70.13%]
  else
    goto <bb 144>; [29.87%]

  <bb 142> [local count: 251634481]:
  if (p_count_732 == 1)
    goto <bb 147>; [5.50%]
  else
    goto <bb 143>; [94.50%]

  <bb 143> [local count: 237794584]:
  # RANGE [irange] int [-INF, -1][1, 2147483646]
  p_count_88 = p_count_732 + -1;

  <bb 144> [local count: 726261510]:
  # p_count_45 = PHI <p_count_732(141), p_count_88(143), p_count_87(140)>
  MEM <unsigned char[20]> [(struct Token *)&Result] = MEM <unsigned char[20]>
[(struct Token *)&I];
  Result$UintData_449 = MEM <const UIntTy> [(struct Token *)&I + 4B];
  Result$PtrData_172 = MEM <void * const> [(struct Token *)&I + 8B];
  Result$16_670 = MEM <unsigned short> [(struct Token *)&I + 16B];
  _439 = TheLexer.D.700857.LexingRawMode;
  if (_439 != 0)
    goto <bb 146>; [99.96%]
  else
    goto <bb 145>; [0.04%]

  <bb 145> [local count: 313395]:
  # USE = nonlocal escaped
  # CLB = nonlocal escaped
  __assert_fail ("LexingRawMode && \"Not already in raw mode!\"",
"/usr/src/llvm-project/clang/include/clang/Lex/Lexer.h", 237, "bool
clang::Lexer::LexFromRawLexer(clang::Token&)");

  <bb 146> [local count: 783176091]:
  # p_count_732 = PHI <p_count_45(144), 0(138)>
  # Result$UintData_591 = PHI <Result$UintData_449(144),
Result$UintData_445(D)(138)>
  # Result$PtrData_270 = PHI <Result$PtrData_172(144),
Result$PtrData_443(D)(138)>
  # Result$16_552 = PHI <Result$16_670(144), Result$16_453(D)(138)>
  # USE = nonlocal escaped { D.1224204 D.1224214 } (escaped)
  # CLB = nonlocal escaped { D.1224204 D.1224214 } (escaped)
  clang::Lexer::Lex (&TheLexer, &I);
  # PT = nonlocal escaped null { D.1224204 D.1224214 } (escaped)
  _440 = TheLexer.BufferPtr;
  # PT = nonlocal escaped null { D.1224204 D.1224214 } (escaped)
  _441 = TheLexer.BufferEnd;
  if (_440 == _441)
    goto <bb 147>; [5.50%]
  else
    goto <bb 139>; [94.50%]

with bb 146 the loop header (before dom2), so I believe Result$16_552 is never
equivalent to _143, it is equivalent to _143 from previous loop's iteration,
not the current one.

[Bug tree-optimization/109462] [13 Regression] Possible miscompilation of clang LocalizationChecker since r13-1938

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109462

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
I have tried
struct Token {
  unsigned char pad[4];
  unsigned int uintdata;
  unsigned long ptrdata;
  unsigned short kind;
  unsigned char pad2[6];
  Token () : uintdata (0), ptrdata (0), kind (0) {}
  unsigned short getKind () { return kind; }
  unsigned int getLength () { return uintdata; }
  unsigned long getLiteralData () { return ptrdata; }
};
bool bar (Token &);
bool baz (unsigned long, unsigned int);
void qux ();
static inline bool
isStringLiteral (unsigned short K)
{
  return ((unsigned short) (K + 65523U) <= 1 || K == 16 || (unsigned short) (K
+ 65519U) <= 1);
}

void
foo ()
{
  Token I;
  Token Result;
  int p_count = 0;
  while (!bar (I)) {
    if (I.getKind () == 21)
      ++p_count;
    if (I.getKind () == 22) {
      if (p_count == 1)
        break;
      --p_count;
    }
    Result = I;
  }
  if (Result.getKind () == 5 || Result.getKind () == 6)
    {
      if (baz (Result.getLiteralData (), Result.getLength ()))
        {
          qux ();
          return;
        }
    }
  if (!isStringLiteral (Result.getKind ()))
    return;
  baz (Result.getLiteralData (), Result.getLength ());
  __builtin_abort ();
}
but while that results in very similar IL, it doesn't reproduce that.

[Bug tree-optimization/109462] [13 Regression] Possible miscompilation of clang LocalizationChecker since r13-1938

[amacleod at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109462

--- Comment #4 from Andrew Macleod <amacleod at redhat dot com> ---
In DOM3 I see
901970   range_on_entry (Result$16_552) to BB 120
<...>
Equivalence update! :  _143 has range  :  [irange] TokenKind [22, 22] NONZERO
0x16 refining range to :[irange] TokenKind [22, 22] NONZERO 0x16
         TRUE : (901970) range_on_entry (Result$16_552) [irange] TokenKind [22,
22] NONZERO 0x16

Because it thinks they are equivlaence, its refining the range to [22,22] which
is the value of _143 on that edge
this traces back to evaluating :

# Result$16_552 = PHI <_143(160), Result$16_453(D)(158)>
where we create an equivalence between Result$16_552 and _143 from bb160.

The reason it is creating the equivalence  is because the value of
Result$16_453(D) is undefined.  It is a local automatic with no initial value. 
When evaluating PHIS, if an incoming range is UNDEFINED, we ignore that
edge/value as it can be anything we choose.
We choose to make it the same as the other argument which allows us to create
an equivlaence between the two.

unsigned short Result$16;

So this boils down to using an uninitialized value for Result$16.

Now the question is where did that come from.

void EmptyLocalizationContextChecker::MethodCrawler::VisitObjCMessageExpr
<...>
  Token Result;
  int p_count = 0;
  while (!TheLexer.LexFromRawLexer(I)) {
    if (I.getKind() == tok::l_paren)
      ++p_count;
    if (I.getKind() == tok::r_paren) {
      if (p_count == 1)
        break;
      --p_count;
    }
    Result = I;
  }

IF the While loop does not execute, then result will be undefined on that edge.
 The code leading to this PHI node is 

<bb 119> [local count: 488466924]:
  if (_143 == 22)
    goto <bb 120>; [70.13%]
  else
    goto <bb 122>; [29.87%]

  <bb 120> [local count: 251634481]:
  if (p_count_732 == 1)
    goto <bb 124>; [5.50%]
  else
    goto <bb 121>; [94.50%]

  <bb 121> [local count: 237794584]:
  p_count_88 = p_count_732 + -1;

  <bb 122> [local count: 726261510]:
  # p_count_45 = PHI <p_count_732(119), p_count_88(121), p_count_87(118)>
  Result$UintData_449 = MEM <const UIntTy> [(struct Token *)&I + 4B];
  Result$PtrData_172 = MEM <void * const> [(struct Token *)&I + 8B];
  _439 = TheLexer.D.700857.LexingRawMode;
  if (_439 != 0)
    goto <bb 160>; [99.96%]
  else
    goto <bb 116>; [0.04%]

  <bb 160> [local count: 725971006]:


So on the path to BB 160 comes from 122 which can come from 119,121 or 118.  It
seems to be using the path oracle and following a path which comes
119->120->121->122->160.    And on that path, the range is indeed [22, 22],
when it ignores the undefined possibility.

Still unclear if this is wrong or not here, and if it is, whetehr ti went wrong
earlier or not.  still analyzing

[Bug tree-optimization/109462] [13 Regression] Possible miscompilation of clang LocalizationChecker since r13-1938

[amacleod at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109462

--- Comment #5 from Andrew Macleod <amacleod at redhat dot com> ---
Created attachment 54835
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=54835&action=edit
in progress patch

THe fix for PR 108139 disallowed an equivalences with a PHI because it may be a
one way equivalence. The PHI may be an equivalence via UNDEFINED arguments so
PHIDEF == name, but name may not be == PHIDEF.

We were checking if the equivalence was a PHI node, buit we were not checking
if the current NAME was a phi node.  SO in this case, 

# Result$16_552 = PHI <_143(160), Result$16_453(D)(158)>

we are evaluating Result$16_552, so the check for _143 from that PR was no
triggering. I think we probably need to also check if the name we are
evaluating is a PHI node as well.

Patch is in testing. I do not know if it fixes the execution test or not, but
it removes the problematic code we were looking at.

[Bug tree-optimization/109462] [13 Regression] Possible miscompilation of clang LocalizationChecker since r13-1938

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109462

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Reduced self-contained testcase, aborts when compiled with r13-1938 and later,
succeeds before that or with the posted patch:

// PR tree-optimization/109462
// { dg-do run { target c++11 } }
// { dg-options "-O2" }

struct A {
  A (const char *);
  A (const char *, int);
  bool empty ();
  int size ();
  bool equals (A);
  A trim (char);
  A trim ();
};
[[gnu::noipa]] A::A (const char *) {}
[[gnu::noipa]] A::A (const char *, int) { __builtin_abort (); }
[[gnu::noipa]] bool A::empty () { __builtin_abort (); }
[[gnu::noipa]] int A::size () { __builtin_abort (); }
[[gnu::noipa]] bool A::equals (A) { return true; }
[[gnu::noipa]] A A::trim (char) { __builtin_abort (); }
[[gnu::noipa]] A A::trim () { __builtin_abort (); }

enum B { raw_identifier = 6, l_paren = 21, r_paren = 22 };
[[gnu::noipa]] bool isAnyIdentifier (B) { return true; }
[[gnu::noipa]] bool isStringLiteral (B) { __builtin_abort (); }

struct C {
  B c;
  B getKind () { return c; }
  bool is (B x) { return c == x; }
  unsigned getLength () { __builtin_abort (); }
  A getRawIdentifier () {
    A x ("");
    c == raw_identifier ? void () : __builtin_abort ();
    return x;
  }
  const char *getLiteralData ();
};
[[gnu::noipa]] const char *C::getLiteralData () { __builtin_abort (); }

struct D {
  D ();
  bool LexFromRawLexer (C &);
};
[[gnu::noipa]] D::D () {}
[[gnu::noipa]] bool D::LexFromRawLexer (C &t) {
  static int cnt;
  C tok[] = { { raw_identifier }, { l_paren }, { raw_identifier }, { r_paren }
};
  t = tok[cnt++];
  return false;
}

bool ok = false;
[[gnu::noipa]] void reportEmptyContextError ()
{
  ok = true;
}

[[gnu::noipa]] void
VisitObjCMessageExpr ()
{
  D TheLexer;
  C I;
  C Result;
  int p_count = 0;
  while (!TheLexer.LexFromRawLexer (I)) {
    if (I.getKind () == l_paren)
      ++p_count;
    if (I.getKind () == r_paren) {
      if (p_count == 1)
        break;
      --p_count;
    }
    Result = I;
  }
  if (isAnyIdentifier (Result.getKind ())) {
    if (Result.getRawIdentifier ().equals ("nil")) {
      reportEmptyContextError ();
      return;
    }
  }
  if (!isStringLiteral (Result.getKind ()))
    return;
  A Comment = A (Result.getLiteralData (), Result.getLength ()).trim ('"');
  if ((Comment.trim ().size () == 0 && Comment.size () > 0) || Comment.empty
())
    reportEmptyContextError ();
}

int
main ()
{
  VisitObjCMessageExpr ();
  if (!ok)
    __builtin_abort ();
}

[Bug tree-optimization/109462] [13 Regression] Possible miscompilation of clang LocalizationChecker since r13-1938

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109462

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2023-04-12

[Bug tree-optimization/109462] [13 Regression] Possible miscompilation of clang LocalizationChecker since r13-1938

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109462

--- Comment #7 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Andrew Macleod <amacleod@gcc.gnu.org>:

https://gcc.gnu.org/g:24af552876eff707f75d30d3f0f0e7a5d62dd857

commit r13-7150-g24af552876eff707f75d30d3f0f0e7a5d62dd857
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Tue Apr 11 17:29:03 2023 -0400

    Don't use ANY PHI equivalences in range-on-entry.

    PR 108139 dissallows PHI equivalencies in the on-entry calculator, but
    it was only checking if the equivlaence was a PHI.  In this case, NAME
    itself is a PHI with an equivlaence caused by an undefined value, so we
    also need to check that case.  Unfortunately this un-fixes 101912.

            PR tree-optimization/109462
            gcc/
            * gimple-range-cache.cc (ranger_cache::fill_block_cache): Don't
            check for equivalences if NAME is a phi node.

            gcc/testsuite/
            * gcc.dg/uninit-pr101912.c: XFAIL the warning.

[Bug tree-optimization/109462] [13 Regression] Possible miscompilation of clang LocalizationChecker since r13-1938

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109462

--- Comment #8 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jakub Jelinek <jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:14f0ea22413fe3e64306c57fbfd2ae7b5769c1a1

commit r13-7151-g14f0ea22413fe3e64306c57fbfd2ae7b5769c1a1
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Wed Apr 12 15:16:31 2023 +0200

    testsuite: Add testcase for recently fixed PR [PR109462]

    This adds a runtime testcase for just fixed PR.

    2023-04-12  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/109462
            * g++.dg/opt/pr109462.C: New test.

[Bug tree-optimization/109462] [13 Regression] Possible miscompilation of clang LocalizationChecker since r13-1938

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109462

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |marxin at gcc dot gnu.org

--- Comment #9 from Martin Liška <marxin at gcc dot gnu.org> ---
Can we close it as fixed?

[Bug tree-optimization/109462] [13 Regression] Possible miscompilation of clang LocalizationChecker since r13-1938

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109462

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|NEW                         |RESOLVED

--- Comment #10 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
The bug is fixed.  Richi posted in the thread that it might be better to limit
the changes to the case where the non-undefined phi arg comes from a backedge,
I guess that can be handled incrementally.

[Bug tree-optimization/109462] [13 Regression] Possible miscompilation of clang LocalizationChecker since r13-1938

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109462

--- Comment #11 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Andrew Macleod <amacleod@gcc.gnu.org>:

https://gcc.gnu.org/g:9c2a5db997446a9438a3e01f5229dec3f78b09e7

commit r13-7170-g9c2a5db997446a9438a3e01f5229dec3f78b09e7
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Wed Apr 12 13:10:55 2023 -0400

    Ensure PHI equivalencies do not dominate the argument edge.

    When we create an equivalency between a PHI definition and an argument,
    ensure the definition does not dominate the incoming argument edge.

            PR tree-optimization/108139
            PR tree-optimization/109462
            * gimple-range-cache.cc (ranger_cache::fill_block_cache): Remove
            equivalency check for PHI nodes.
            * gimple-range-fold.cc (fold_using_range::range_of_phi): Ensure def
            does not dominate single-arg equivalency edges.