Last Comment Bug 733863 - Clang-compiled js::mjit::LoopState::hoistArrayLengthCheck confuses valgrind into reporting UMR
: Clang-compiled js::mjit::LoopState::hoistArrayLengthCheck confuses valgrind i...
Status: RESOLVED FIXED
[llvm bug]
: testcase, valgrind
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: Trunk
: x86 Mac OS X
: -- critical (vote)
: mozilla15
Assigned To: Julian Seward [:jseward]
:
Mentors:
: 733866 (view as bug list)
Depends on:
Blocks: jsfunfuzz
  Show dependency treegraph
 
Reported: 2012-03-07 11:54 PST by Gary Kwong [:gkw] [:nth10sd]
Modified: 2012-05-04 03:58 PDT (History)
9 users (show)
ryanvm: in‑testsuite-
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
initialise outparams as per comment 7 (958 bytes, patch)
2012-04-17 10:00 PDT, Julian Seward [:jseward]
bhackett1024: review+
Details | Diff | Review
Initialise outparams in callee (LoopState::getEntryValue) rather than at all call points (855 bytes, patch)
2012-04-17 10:34 PDT, Julian Seward [:jseward]
bhackett1024: review+
Details | Diff | Review
As previous patch, with comment removed (697 bytes, patch)
2012-04-18 00:17 PDT, Julian Seward [:jseward]
no flags Details | Diff | Review

Description Gary Kwong [:gkw] [:nth10sd] 2012-03-07 11:54:34 PST
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.
Comment 1 Gary Kwong [:gkw] [:nth10sd] 2012-03-15 13:41:36 PDT
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.
Comment 2 Brian Hackett (:bhackett) 2012-03-15 13:50:21 PDT
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.
Comment 3 Gary Kwong [:gkw] [:nth10sd] 2012-03-15 13:53:30 PDT
(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?
Comment 4 Julian Seward [:jseward] 2012-03-15 17:51:20 PDT
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 Jesse Ruderman 2012-03-15 18:55:10 PDT
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?
Comment 6 Julian Seward [:jseward] 2012-03-16 01:35:18 PDT
> 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;
Comment 7 Brian Hackett (:bhackett) 2012-03-16 02:11:47 PDT
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 Jesse Ruderman 2012-03-16 05:46:11 PDT
>   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?
Comment 9 Julian Seward [:jseward] 2012-03-20 11:26:26 PDT
(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) ?
Comment 10 Rafael Ávila de Espíndola (:espindola) (not reading bugmail) 2012-03-20 15:20:10 PDT
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
Comment 11 Rafael Ávila de Espíndola (:espindola) (not reading bugmail) 2012-03-20 15:33:38 PDT
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 Jesse Ruderman 2012-03-20 16:44:49 PDT
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).
Comment 13 Rafael Ávila de Espíndola (:espindola) (not reading bugmail) 2012-03-20 17:09:26 PDT
I see. It might be a good idea reporting a bug to llvm.org. Maybe we do need a  --be-nice-to-valgrind option.
Comment 14 Rafael Ávila de Espíndola (:espindola) (not reading bugmail) 2012-03-20 17:39:56 PDT
I reported llvm.org/pr12319
Comment 15 Gary Kwong [:gkw] [:nth10sd] 2012-04-06 17:10:22 PDT
LLVM bug, see http://llvm.org/bugs/show_bug.cgi?id=12319
Comment 16 Gary Kwong [:gkw] [:nth10sd] 2012-04-06 17:12:01 PDT
*** Bug 733866 has been marked as a duplicate of this bug. ***
Comment 17 Rafael Ávila de Espíndola (:espindola) (not reading bugmail) 2012-04-09 07:15:53 PDT
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 Jesse Ruderman 2012-04-09 09:10:51 PDT
"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?
Comment 19 Rafael Ávila de Espíndola (:espindola) (not reading bugmail) 2012-04-09 09:48:48 PDT
(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.
Comment 20 Julian Seward [:jseward] 2012-04-17 10:00:37 PDT
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.
Comment 21 Gary Kwong [:gkw] [:nth10sd] 2012-04-17 10:03:16 PDT
Reopening since there's a patch available to possibly alleviate the issue.
Comment 22 Julian Seward [:jseward] 2012-04-17 10:34:21 PDT
Created attachment 615776 [details] [diff] [review]
Initialise outparams in callee (LoopState::getEntryValue) rather than at all call points
Comment 23 Brian Hackett (:bhackett) 2012-04-17 10:38:00 PDT
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).
Comment 24 Julian Seward [:jseward] 2012-04-18 00:17:00 PDT
Created attachment 616038 [details] [diff] [review]
As previous patch, with comment removed
Comment 25 Gary Kwong [:gkw] [:nth10sd] 2012-04-23 23:20:57 PDT
(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?
Comment 26 Julian Seward [:jseward] 2012-05-01 13:24:25 PDT
Yes, is ready to go, passed try.
Comment 27 Ryan VanderMeulen [:RyanVM] 2012-05-03 03:57:28 PDT
https://hg.mozilla.org/integration/mozilla-inbound/rev/38921cd42448
Comment 28 Ed Morley [:emorley] 2012-05-04 03:58:03 PDT
https://hg.mozilla.org/mozilla-central/rev/38921cd42448

Note You need to log in before you can comment on or make changes to this bug.