Right now they live in rustc_data_structures, but we can rely on crates now. It'd be nicer if they were over in a rust-lang crate, which would let us optimize, test, and otherwise develop them independently from rustc. (It'd also be useful in projects like borrow-check). As you can see in this comment, the current plan is to begin doing this "in tree" and only later decide whether to move out of tree.