[IntervalTree] Initialize find_iterator::Point

[caojoshua]

Summary

There was initially a msan report for use-of-uninitialized value due to
a bug in https://reviews.llvm.org/D138526. find_iterator::Point is
uninitialized for the default constructor of find_iterator, which is
used by IntervalTree::end. This change is not required, but its good
practice to make sure all class members are initialized.

[caojoshua]

If this change looks ok, I would like to reland https://reviews.llvm.org/D138526

[caojoshua]

We can't rely on the compiler to short-circuit the conditional check in find_iterator::operator==().

return (!LHS.Node && !RHS.Node && !LHS.Index && !RHS.Index) ||
       (LHS.Point == RHS.Point && LHS.Node == RHS.Node &&
        LHS.Index == RHS.Index);

Before the unswitch patch, the compiler was short-circuiting, so we never use the uninitialized RHS.Point. After the unswitching patch, the RHS of the || gets hoisted to an earlier part of the function.

The compiler is legally allowed to switch the left hand and right hand side of the ||. I constructed an example in https://godbolt.org/z/MvdzdKovz.

[vitalybuka]

In D149698#4313832, @caojoshua wrote:

We can't rely on the compiler to short-circuit the conditional check in find_iterator::operator==().

return (!LHS.Node && !RHS.Node && !LHS.Index && !RHS.Index) ||
       (LHS.Point == RHS.Point && LHS.Node == RHS.Node &&
        LHS.Index == RHS.Index);

Before the unswitch patch, the compiler was short-circuiting, so we never use the uninitialized RHS.Point. After the unswitching patch, the RHS of the || gets hoisted to an earlier part of the function.

The compiler is legally allowed to switch the left hand and right hand side of the ||. I constructed an example in https://godbolt.org/z/MvdzdKovz.

Comment in https://godbolt.org/z/MvdzdKovz is incorrect, x is zero initialized as it's global. But I am not sure what this proves.

There is c/c++ standard and the is compiler. Standard explain how such expressions are evaluated. I believe this is short circuited. Compiler can do shortcuts if results the same.

However Msan goal is to detect undefined behaviors in user code when the user violates standard.
D138526 brakes msan, making it falsely complaining when violation is not really happening, like here.

foo in your example is not a problem as select is pass-through for msan. it complains about branches.
When you replace select with branch, we have a report.

llvm/include/llvm/ADT/IntervalTree.h

466

it should be here

[caojoshua]

• zero initialize Point
• update commit message to show this is NFC. there is no true use-of-uninitialized bug in IntervalTree, just a bug in the unswitching patch

I don't want to push this until https://reviews.llvm.org/D138526 is merged and is not causing any test issues. I fixed that patch to pass the affected test locally, but want to confirm on buildbot builds.

[CarlosAlbertoEnciso]

llvm/include/llvm/ADT/IntervalTree.h

466

LGTM

[vitalybuka]

I don't see problem with the patch and prefer to initialized as much as possible.
However there is an opinion that keeping stuff uninitialized may help msan to catch holes in logic if code missed real initialization.
Seems @CarlosAlbertoEnciso is OK

llvm/include/llvm/ADT/IntervalTree.h

public:
 
   private:
     const IntervalReferences *AscendingBuckets = nullptr;
     const IntervalReferences *DescendingBuckets = nullptr;
 
     // Current node and index while traversing the intervals that contain
     // the reference point.
     IntervalNode *Node = nullptr;
-    PointType Point;
+    PointType Point = {};
     unsigned Index = 0;
 
     // For the current node, check if we have intervals that contain the
     // reference point. We return when the node does have intervals that
     // contain such point. Otherwise we keep descending on that branch.
     void initNode() {
       Index = 0;
       while (Node) {