Index: sys/sys/tree.h
===================================================================
--- sys/sys/tree.h
+++ sys/sys/tree.h
@@ -535,16 +535,25 @@
 	 * with a black non-null child and a red null child. The        \
 	 * balance criterion "the rank of any leaf is 1" precludes the  \
 	 * possibility of two red null children for the initial parent. \
-	 * So the first loop iteration cannot lead to accessing an      \
-	 * uninitialized 'child', and a later iteration can only happen \
-	 * when a value has been assigned to 'child' in the previous    \
-	 * one.								\
 	 */								\
 	struct type *child, *child_up, *gpar;				\
 	__uintptr_t elmdir, sibdir;					\
 									\
-	do {								\
-		/* the rank of the tree rooted at elm grew */		\
+	gpar = _RB_UP(parent, field);					\
+	elmdir = RB_RIGHT(parent, field) == elm ? _RB_R : _RB_L;	\
+	if (_RB_BITS(gpar) & elmdir) {					\
+		/* shorten the parent-elm edge to rebalance */		\
+		_RB_MOD_XOR(_RB_UP(parent, field), elmdir);		\
+		return (NULL);						\
+	}								\
+	do  {								\
+		/* the other edge must change length */			\
+		_RB_MOD_XOR(_RB_UP(parent, field), elmdir ^ _RB_LR);	\
+		if (gpar == NULL)					\
+			return (NULL);					\
+		child = elm;						\
+		elm = parent;						\
+		parent = gpar;						\
 		gpar = _RB_UP(parent, field);				\
 		elmdir = RB_RIGHT(parent, field) == elm ? _RB_R : _RB_L; \
 		if (_RB_BITS(gpar) & elmdir) {				\
@@ -552,82 +561,70 @@
 			_RB_MOD_XOR(_RB_UP(parent, field), elmdir);	\
 			return (NULL);					\
 		}							\
-		sibdir = elmdir ^ _RB_LR;				\
-		/* the other edge must change length */			\
-		_RB_MOD_XOR(_RB_UP(parent, field), sibdir);		\
-		if ((_RB_BITS(gpar) & _RB_LR) == 0) {			\
-			/* both edges now short, retry from parent */	\
-			child = elm;					\
-			elm = parent;					\
-			continue;					\
-		}							\
-		_RB_UP(parent, field) = gpar = _RB_PTR(gpar);		\
-		if (_RB_BITSUP(elm, field) & elmdir) {			\
-			/*						\
-			 * Exactly one of the edges descending from elm \
-			 * is long. The long one is in the same		\
-			 * direction as the edge from parent to elm,	\
-			 * so change that by rotation.  The edge from	\
-			 * parent to z was shortened above.  Shorten	\
-			 * the long edge down from elm, and adjust	\
-			 * other edge lengths based on the downward	\
-			 * edges from 'child'.				\
-			 *						\
-			 *	     par		 par		\
-			 *	    /	\		/   \		\
-			 *	  elm	 z	       /     z		\
-			 *	 /  \		     child		\
-			 *	/  child	     /	 \		\
-			 *     /   /  \		   elm	  \		\
-			 *    w	  /    \	  /   \    y		\
-			 *	 x      y	 w     \		\
-			 *				x		\
-			 */						\
-			RB_ROTATE(elm, child, elmdir, field);		\
-			child_up = _RB_UP(child, field);		\
-			if (_RB_BITS(child_up) & sibdir)		\
-				_RB_MOD_XOR(_RB_UP(parent, field),	\
-				    elmdir); 				\
-			if (_RB_BITS(child_up) & elmdir)		\
-				_RB_MOD_XOR(_RB_UP(elm, field),		\
-				    _RB_LR);				\
-			else						\
-				_RB_MOD_XOR(_RB_UP(elm, field),		\
-				    elmdir);				\
-			/* if child is a leaf, don't augment elm,	\
-			 * since it is restored to be a leaf again. */	\
-			if ((_RB_BITS(child_up) & _RB_LR) == 0)		\
-				elm = child;				\
-		} else							\
-			child = elm;					\
-									\
+	} while ((_RB_BITS(gpar) & _RB_LR) == 0);			\
+	sibdir = elmdir ^ _RB_LR;					\
+	_RB_UP(parent, field) = gpar = _RB_PTR(gpar);			\
+	if (_RB_BITSUP(elm, field) & elmdir) {				\
 		/*							\
-		 * The long edge descending from 'child' points back	\
-		 * in the direction of 'parent'. Rotate to make		\
-		 * 'parent' a child of 'child', then make both edges	\
-		 * of 'child' short to rebalance.			\
+		 * Exactly one of the edges descending from elm		\
+		 * is long. The long one is in the same			\
+		 * direction as the edge from parent to elm,		\
+		 * so change that by rotation.  The edge from		\
+		 * parent to z was shortened above.  Shorten		\
+		 * the long edge down from elm, and adjust		\
+		 * other edge lengths based on the downward		\
+		 * edges from 'child'.					\
 		 *							\
-		 *	     par		 child			\
-		 *	    /	\		/     \			\
-		 *	   /	 z	       x       par		\
-		 *	child			      /	  \		\
-		 *	 /  \			     /	   z		\
-		 *	x    \			    y			\
-		 *	      y						\
-		 */							\
-		RB_ROTATE(parent, child, sibdir, field);		\
-		_RB_UP(child, field) = gpar;				\
-		RB_SWAP_CHILD(head, gpar, parent, child, field);	\
-		/*							\
-		 * Elements rotated down have new, smaller subtrees,	\
-		 * so update augmentation for them.			\
+		 *	     par		 par			\
+		 *	    /	\		/   \			\
+		 *	  elm	 z	       /     z			\
+		 *	 /  \		     child			\
+		 *	/  child	     /	 \			\
+		 *     /   /  \		   elm	  \			\
+		 *    w	  /    \	  /   \    y			\
+		 *	 x      y	 w     \			\
+		 *				x			\
 		 */							\
-		if (elm != child)					\
-			(void)RB_AUGMENT_CHECK(elm);			\
-		(void)RB_AUGMENT_CHECK(parent);				\
-		return (child);						\
-	} while ((parent = gpar) != NULL);				\
-	return (NULL);							\
+		RB_ROTATE(elm, child, elmdir, field);			\
+		child_up = _RB_UP(child, field);			\
+		if (_RB_BITS(child_up) & sibdir)			\
+			_RB_MOD_XOR(_RB_UP(parent, field), elmdir);	\
+		if (_RB_BITS(child_up) & elmdir)			\
+			_RB_MOD_XOR(_RB_UP(elm, field), _RB_LR);	\
+		else							\
+			_RB_MOD_XOR(_RB_UP(elm, field), elmdir);	\
+		/* if child is a leaf, don't augment elm,		\
+		 * since it is restored to be a leaf again. */		\
+		if ((_RB_BITS(child_up) & _RB_LR) == 0)			\
+			elm = child;					\
+	} else								\
+		child = elm;						\
+									\
+	/*								\
+	 * The long edge descending from 'child' points back		\
+	 * in the direction of 'parent'. Rotate to make			\
+	 * 'parent' a child of 'child', then make both edges		\
+	 * of 'child' short to rebalance.				\
+	 *								\
+	 *	     par		 child				\
+	 *	    /	\		/     \				\
+	 *	   /	 z	       x       par			\
+	 *	child			      /	  \			\
+	 *	 /  \			     /	   z			\
+	 *	x    \			    y				\
+	 *	      y							\
+	 */								\
+	RB_ROTATE(parent, child, sibdir, field);			\
+	_RB_UP(child, field) = gpar;					\
+	RB_SWAP_CHILD(head, gpar, parent, child, field);		\
+	/*								\
+	 * Elements rotated down have new, smaller subtrees,		\
+	 * so update augmentation for them.				\
+	 */								\
+	if (elm != child)						\
+		(void)RB_AUGMENT_CHECK(elm);				\
+	(void)RB_AUGMENT_CHECK(parent);					\
+	return (child);							\
 }
 
 #ifndef RB_STRICT_HST