The default bug view has changed. See this FAQ.

Clang-compiled js::mjit::LoopState::hoistArrayLengthCheck confuses valgrind into reporting UMR

RESOLVED FIXED in mozilla15

Status

()

Core
JavaScript Engine
--
critical
RESOLVED FIXED
5 years ago
5 years ago

People

(Reporter: gkw, Assigned: jseward)

Tracking

(Blocks: 1 bug, {testcase, valgrind})

Trunk
mozilla15
x86
Mac OS X
testcase, valgrind
Points:
---
Bug Flags:
in-testsuite -

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [llvm bug])

Attachments

(1 attachment, 2 obsolete attachments)

(Reporter)

Description

5 years ago
var a = [];
for (var i = 0; a < 9; ++i) {
  a[i] = "";
}

on a js opt 64-bit shell on m-c changeset 3dcb40ebd487 with -m, -a and -n shows up:

==24616== Conditional jump or move depends on uninitialised value(s)
==24616==    at 0x1001EBF8B: js::mjit::LoopState::hoistArrayLengthCheck(js::mjit::InvariantArrayKind, js::analyze::CrossSSAValue const&, js::analyze::CrossSSAValue const&) (jsanalyze.h:1127)
==24616==    by 0x1001DBAEF: js::mjit::Compiler::jsop_setelem_dense() (FastOps.cpp:1112)
==24616==    by 0x1001DDF07: js::mjit::Compiler::jsop_setelem(bool) (FastOps.cpp:1551)
==24616==    by 0x100187EE5: js::mjit::Compiler::generateMethod() (Compiler.cpp:2570)
==24616==    by 0x100185658: js::mjit::Compiler::performCompilation() (Compiler.cpp:548)
==24616==    by 0x100191F79: js::mjit::CanMethodJIT(JSContext*, JSScript*, unsigned char*, bool, js::mjit::CompileRequest) (Compiler.cpp:148)
==24616==    by 0x10006E9B8: js::Interpret(JSContext*, js::StackFrame*, js::InterpMode) (jsinterp.cpp:1703)
==24616==    by 0x1001796AC: js::mjit::JaegerShot(JSContext*, bool) (MethodJIT.cpp:1079)
==24616==    by 0x10006DC13: js::RunScript(JSContext*, JSScript*, js::StackFrame*) (jsinterp.cpp:466)
==24616==    by 0x10007A82D: js::ExecuteKernel(JSContext*, JSScript*, JSObject&, JS::Value const&, js::ExecuteType, js::StackFrame*, JS::Value*) (jsinterp.cpp:668)
==24616==    by 0x10007A996: js::Execute(JSContext*, JSScript*, JSObject&, JS::Value*) (jsinterp.cpp:709)
==24616==    by 0x10001844A: JS_ExecuteScript (jsapi.cpp:5285)
==24616==  Uninitialised value was created by a stack allocation
==24616==    at 0x1001EBF38: js::mjit::LoopState::hoistArrayLengthCheck(js::mjit::InvariantArrayKind, js::analyze::CrossSSAValue const&, js::analyze::CrossSSAValue const&) (LoopState.cpp:523)
==24616== 

valgrind --track-origins=yes --smc-check=all-non-file --dsymutil=yes ./js -m -a -n testcase.js

I'm on Valgrind r12423.
(Reporter)

Updated

5 years ago
Summary: Conditional jump or move depends on uninitialised value running valgrind with testcase → Conditional jump or move depends on uninitialised value with js::mjit::LoopState::hoistArrayLengthCheck on the stack running valgrind with testcase
(Reporter)

Comment 1

5 years ago
This bug blocks fuzzing w/ Valgrind to find conditional jump issues, see also bug 733866.

Brian, any ideas? You might need to compile Valgrind off SVN to get some recent Valgrind fixes too.
I think this has been reported before and that it is a false positive.  The code involved is accessing an array of bools, and the access is definitely in bounds and getting initialized memory.
(Reporter)

Comment 3

5 years ago
(In reply to Brian Hackett (:bhackett) from comment #2)
> I think this has been reported before and that it is a false positive.  The
> code involved is accessing an array of bools, and the access is definitely
> in bounds and getting initialized memory.

Thanks for the clarification, Brian.

Julian, perhaps this is a testcase you'd need regarding a Valgrind false positive?
(Assignee)

Comment 4

5 years ago
I'm just wondering if this is a bug in LLVM.  After sticking in a
couple of __attribute__((noinline))s, the V complaint moves to
LoopState.cpp:535, viz:

533   uint32_t objSlot;
534   int32_t objConstant;
535   if (!getEntryValue(obj, &objSlot, &objConstant) || objSlot == UNASSIGNED || objConstant != 0)
536       return false;

Rewriting like this makes the complaint go away, curiously:

   bool b = getEntryValue(obj, &objSlot, &objConstant);
   if (!b) return false;
   if (objSlot == UNASSIGNED) return false;
   if (objConstant != 0) return false;

Comparing assembly for the two versions is interesting.  For this
flattened out version, we have

   callq   __ZN2js4mjit9LoopState13getEntryValueERKNS_7analyze13CrossSSAValueEPjPi
   movb    %al,%cl
   xorb    %al,%al
   testb   %cl,%cl
   je      0x1001e6dda
   xorb    %al,%al
   movl    0xffffff6c(%rbp),%ecx
   movl    %ecx,0xffffff58(%rbp)
   cmpl    $0xff,%ecx
   je      0x1001e6dda
   xorb    %al,%al
   cmpl    $0x00,0xffffff68(%rbp)
   jne     0x1001e6dda

so the first conditional branch after the call to getEntryValue does
test its return value.  But the code from the original line 535 is:

   callq   __ZN2js4mjit9LoopState13getEntryValueERKNS_7analyze13CrossSSAValueEPjPi
   movb    %al,%cl
   xorb    %al,%al
   movl    0xffffff6c(%rbp),%edx
   movl    %edx,0xffffff58(%rbp)
   cmpl    $0xff,%edx
   je      0x1001e6dda
   xorb    $0x01,%cl
   testb   %cl,%cl
   jne     0x1001e6dda
   movl    0xffffff68(%rbp),%ecx
   testl   %ecx,%ecx
   jne     0x1001e6dda

Unless I misinterpret, the first conditional branch after the call
depends on some value hauled off the stack, from 0xffffff6c(%rbp),
which is presumably either objSlot or objConstant.  So it's as if
LLVM had compiled this

   bool b = getEntryValue(obj, &objSlot, &objConstant);
   if (objSlot == UNASSIGNED) return false;
   if (!b) return false;
   if (objConstant != 0) return false;

If getEntryValue returns false then it doesn't write to either
objSlot or objConstant, so the V warning is correct.

Sanity checks on the above analysis welcomed ..

Comment 5

5 years ago
That seems like a valid code transformation to me; it won't cause the code to actually misbehave.

Does clang have a --be-nice-to-valgrind mode?
(Assignee)

Comment 6

5 years ago
> That seems like a valid code transformation to me;

Sheesh -- yes.  Bizarre.  I've never seen such a thing before.  I
wonder what the essence of it is ..  I can't figure that out.
Something along the lines of

  if (A || B) { ... }   ===>   if (B || A) { ... }
  when B has no side effects and there's some relationship
  between B and A -- but what?

I did think it was strange that a stable production version of clang
(vanilla 3.0) would produce such an obviously borked bit of code, and
also that js worked despite it :)

What's also strange is that the translation clang has used is less
efficient in the case where getEntryValue returns false.  In that case
it takes either 1 or 2 conditional branches to get to "return false;",
depending on what junk is parked in objSlot.  In the more obvious
translation, it's guaranteed to require only one conditional branch.

Not sure what I can do about it in V though.  We could work around it
by giving initial values for objSlot and objConstant (inefficient) or
(better) by forcing a sequence point:

  if (!getEntryValue(obj, &objSlot, &objConstant)) return false;
  if (objSlot == UNASSIGNED || objConstant != 0) return false;
Either of those fixes would be fine, though the first is probably better --- this code is cold, and it's good practice to initialize outparams on all return paths.

Comment 8

5 years ago
>   if (A || B) { ... }   ===>   if (B || A) { ... }
>   when B has no side effects and there's some relationship
>   between B and A -- but what?

Maybe some part of the compiler thinks reading A will cause a pipeline stall, but reading B won't?
(Assignee)

Comment 9

5 years ago
(In reply to Jesse Ruderman from comment #8)
> >   if (A || B) { ... }   ===>   if (B || A) { ... }
> >   when B has no side effects and there's some relationship
> >   between B and A -- but what?

On reflection, I think I'd like to know two things about this:

(1) that it's actually intended, and not a bug in LLVM

(2) assuming it is intended, what are the conditions under
    which the transformation is valid (safe) ?
Looks like this is happening during codegen. I reduced it to a simple function with a series of ors. Just before codegen the IL looks like

define zeroext i1 @g(i32* %objSlot, i32* %objConstant) uwtable align 2 {
  %call = call zeroext i1 @f()
  %tmp2 = load i32* %objSlot, align 4
  %cmp = icmp eq i32 %tmp2, -1
  %or.cond = or i1 %cmp, %call
  %tmp3 = load i32* %objConstant, align 4
  %cmp3 = icmp ne i32 %tmp3, 0
  %or.cond64 = or i1 %or.cond, %cmp3
  br i1 %or.cond64, label %return, label %if.end5

return:                                           ; preds = %0
  ret i1 true

if.end5:                                          ; preds = %0
  ret i1 false
}

But codegen splits the first basic block for some reason, choosing to split it like

BB#0: derived from LLVM BB %0
    Live Ins: %RDI %RSI
        %vreg1<def> = COPY %RSI; GR64:%vreg1
        %vreg0<def> = COPY %RDI; GR64:%vreg0
        ADJCALLSTACKDOWN64 0, %RSP<imp-def,dead>, %EFLAGS<imp-def,dead>, %RSP<imp-use>
        CALL64pcrel32 <ga:@f>, <regmask>, %RSP<imp-use>, %RSP<imp-def>, %AL<imp-def>
        ADJCALLSTACKUP64 0, 0, %RSP<imp-def,dead>, %EFLAGS<imp-def,dead>, %RSP<imp-use>
        %vreg4<def> = COPY %AL; GR8:%vreg4
        %vreg3<def> = MOV32rm %vreg1, 1, %noreg, 0, %noreg; mem:LD4[%objConstant] GR32:%vreg3 GR64:%vreg1
        %vreg2<def> = COPY %vreg4; GR8:%vreg2,%vreg4
        CMP32mi8 %vreg0, 1, %noreg, 0, %noreg, -1, %EFLAGS<imp-def>; mem:LD4[%objSlot] GR64:%vreg0
        JE_4 <BB#1>, %EFLAGS<imp-use>
        JMP_4 <BB#4>
    Successors according to CFG: BB#1 BB#4

debugging a bit more why it decided to do it
The BB splitting is coming from:

  // If this is a series of conditions that are or'd or and'd together, emit
  // this as a sequence of branches instead of setcc's with and/or operations.
  // As long as jumps are not expensive, this should improve performance.
  // For example, instead of something like:
  //     cmp A, B
  //     C = seteq
  //     cmp D, E
  //     F = setle
  //     or C, F
  //     jnz foo
  // Emit:
  //     cmp A, B
  //     je foo
  //     cmp D, E
  //     jle foo
  //

In SelectionDAGBuilder.cpp. So what we are seeing in this bug is a combination of that and the original order being lost in the IL. Let me know if there is a bug in this heuristic (or if it causes performance problems).

Why does this transformation causes problem to valgrind?

Comment 12

5 years ago
If getEntryValue returns false then it doesn't write to either objSlot or objConstant.

if (!getEntryValue(obj, &objSlot, &objConstant) || objSlot == UNASSIGNED || objConstant != 0)

Memcheck's heuristic for what constitutes a "use" of uninitialized memory is a conditional move/jump or a system call.  So when the compiled code does its (first) conditional jump based (only) on objSlot, Memcheck sees that as an uninitialized use (in the case where getEntryValue returns false).
I see. It might be a good idea reporting a bug to llvm.org. Maybe we do need a  --be-nice-to-valgrind option.
I reported llvm.org/pr12319

Updated

5 years ago
Summary: Conditional jump or move depends on uninitialised value with js::mjit::LoopState::hoistArrayLengthCheck on the stack running valgrind with testcase → Clang-compiled js::mjit::LoopState::hoistArrayLengthCheck confuses valgrind into reporting UMR
(Reporter)

Comment 15

5 years ago
LLVM bug, see http://llvm.org/bugs/show_bug.cgi?id=12319
Status: NEW → RESOLVED
Last Resolved: 5 years ago
Resolution: --- → INVALID
Whiteboard: js-triage-needed → llvm bug
(Reporter)

Updated

5 years ago
Duplicate of this bug: 733866
(Reporter)

Updated

5 years ago
Whiteboard: llvm bug → [llvm bug]
Not sure invalid is the right fix in here. The transformation is valid, it is just very hard for valgrind to see that.

Comment 18

5 years ago
"Invalid because it's an LLVM bug rather than a Firefox bug". Or do you think we should change the Firefox code to work around the problem?
(In reply to Jesse Ruderman from comment #18)
> "Invalid because it's an LLVM bug rather than a Firefox bug". Or do you
> think we should change the Firefox code to work around the problem?

Not sure. Probably depends on how likely this is to be fixed in valgrind or worked around in llvm.

Comment 7 suggests it might be OK to workaround the problem is our code.
(Assignee)

Comment 20

5 years ago
Created attachment 615758 [details] [diff] [review]
initialise outparams as per comment 7

The patch initialises objSlot and objConstant in such a way
that if the call to getEntryValue fails to set either of them,
then we exit the routine at the if(..), returning false, rather
than continuing into the body of the routine.  This seems a safe
approach.
(Assignee)

Updated

5 years ago
Attachment #615758 - Flags: review?(bhackett1024)
(Reporter)

Comment 21

5 years ago
Reopening since there's a patch available to possibly alleviate the issue.
Status: RESOLVED → REOPENED
Resolution: INVALID → ---
Attachment #615758 - Flags: review?(bhackett1024) → review+
(Assignee)

Comment 22

5 years ago
Created attachment 615776 [details] [diff] [review]
Initialise outparams in callee (LoopState::getEntryValue) rather than at all call points
Attachment #615758 - Attachment is obsolete: true
Attachment #615776 - Flags: review?(bhackett1024)
Comment on attachment 615776 [details] [diff] [review]
Initialise outparams in callee (LoopState::getEntryValue) rather than at all call points

Review of attachment 615776 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/methodjit/LoopState.cpp
@@ +2088,5 @@
>  bool
>  LoopState::getEntryValue(const CrossSSAValue &iv, uint32_t *pslot, int32_t *pconstant)
>  {
> +    /* Set out params to values that work around a Valgrind false positive in the
> +       case where we return 'false'.  See bug 733863 and (dup) 733866. */

I don't think this comment is necessary.  Also, JS comments should have the /* and */ on their own line (e.g. see the comment below this change).
Attachment #615776 - Flags: review?(bhackett1024) → review+
(Assignee)

Comment 24

5 years ago
Created attachment 616038 [details] [diff] [review]
As previous patch, with comment removed
Attachment #615776 - Attachment is obsolete: true
(Reporter)

Comment 25

5 years ago
(In reply to Julian Seward from comment #24)
> Created attachment 616038 [details] [diff] [review]
> As previous patch, with comment removed

Julian, is this patch ready for review and/or landing?
(Assignee)

Comment 26

5 years ago
Yes, is ready to go, passed try.
(Assignee)

Updated

5 years ago
Keywords: checkin-needed
https://hg.mozilla.org/integration/mozilla-inbound/rev/38921cd42448
Flags: in-testsuite-
Keywords: checkin-needed
Target Milestone: --- → mozilla15
Assignee: general → jseward
https://hg.mozilla.org/mozilla-central/rev/38921cd42448
Status: REOPENED → RESOLVED
Last Resolved: 5 years ago5 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.