On Friday 26 February 2010 19:09:01 Dan Gohman wrote:> I've now looked at your latest patch. In summary, it does expose a > subtle problem. I haven't seen anything that here would lead to > observable misbehavior yet though.Well, I'm definitely observing misbehavior. I know it has something to do with local changes here but I haven't isolated it yet.> X86GenDAGISel.inc has code like this: > > SDValue N1 = N->getOperand(1); > ... > SDNode *ResNode = CurDAG->SelectNodeTo(N, ...); > ... > ReplaceUses(SDValue(N1.getNode(), 1), SDValue(ResNode, 2)); > > If N was the only user of N1, and N1 isn't in the new operand list, then > the SelectNodeTo call will make N1 dead. SelectNodeTo will automatically > delete nodes that are made dead by the transformation. This means that > the "from" node in the subsequent ReplaceUses call will be a deleted > node > in that case.Ok, so that should be easy to fix.> This doesn't break in practice because deleted node aren't actually > deallocated, they're just put on a linked list of nodes ready to be > reused next time a new node is created, and no new nodes are created > between the SelectNodeTo call and the ReplaceUses call.Right.> Another observation here is that the ReplaceUses call in such cases > doesn't do anything, because the From node has no uses.Right.> Perhaps this can be fixed by making the code skip the ReplaceUses > call in the case where there are no uses to replace. That's not trivial > to detect though.Why not just check the same thing the added asserts check? What I'm seeing is a problem in ReplaceAllUsesOf itself. It recurses down and eventually replaces the node under the iterator in this use loop: SDNode::use_iterator UI = From.getNode()->use_begin(), UE = From.getNode()->use_end(); while (UI != UE) { SDNode *User = *UI; bool UserRemovedFromCSEMaps = false; UI goes bad and we blow up after returning from a deeply recursed call. It's simply not safe to iterate over a set that may change. Unfortunately, any of the nodes under the iterators may change so I don't see an easy way to fix this. -Dave
On Mar 1, 2010, at 7:26 AM, David Greene wrote:> >> Perhaps this can be fixed by making the code skip the ReplaceUses >> call in the case where there are no uses to replace. That's not trivial >> to detect though. > > Why not just check the same thing the added asserts check?You mean ->getOpcode() == ISD::DELETED_NODE? That's not fundamentally any better, because if your purpose is to make this code work even if nodes are actually deleted, that would still be a use of free'd memory.> > What I'm seeing is a problem in ReplaceAllUsesOf itself. It recurses > down and eventually replaces the node under the iterator in this use > loop: > > SDNode::use_iterator UI = From.getNode()->use_begin(), > UE = From.getNode()->use_end(); > while (UI != UE) { > SDNode *User = *UI; > bool UserRemovedFromCSEMaps = false; > > > UI goes bad and we blow up after returning from a deeply recursed call. > > It's simply not safe to iterate over a set that may change. Unfortunately, > any of the nodes under the iterators may change so I don't see an easy > way to fix this.The thing it's iterating over is a linked list. And the use_end() iterator is essentially a null pointer. Dan
On Monday 01 March 2010 13:41:12 Dan Gohman wrote:> On Mar 1, 2010, at 7:26 AM, David Greene wrote: > >> Perhaps this can be fixed by making the code skip the ReplaceUses > >> call in the case where there are no uses to replace. That's not trivial > >> to detect though. > > > > Why not just check the same thing the added asserts check? > > You mean ->getOpcode() == ISD::DELETED_NODE? That's not fundamentally > any better, because if your purpose is to make this code work even > if nodes are actually deleted, that would still be a use of free'd > memory.Wait, I thought memory wasn't actually freed, just returned to a free list.> > UI goes bad and we blow up after returning from a deeply recursed call. > > > > It's simply not safe to iterate over a set that may change. > > Unfortunately, any of the nodes under the iterators may change so I don't > > see an easy way to fix this. > > The thing it's iterating over is a linked list. And the use_end() iterator > is essentially a null pointer.No, what I mean is the thing under UI at the point of call to AddModifiedNodeToCSEMaps gets deleted. So UI is invalid and when we loop back around and check it against UE we blow up with a singular iterator error. I can add code to save a few values of UI, find one that "works" after AddModifiedNodeToCSEMaps and get llc to finish. But that's a horrible hack only meant to prove that this is actually the problem. We're essentially doing this: std::list<...>::iterator i = ... for (... i != list.end(); ++i) { foo(i); } foo(iterator i) { list.erase(i); } -Dave