What would be the best way to store custom data with each LLVM instruction node? Say to pass information from one pass to another? It doesn't seem like the instruction class allows users to store arbitrary data?
You can associate any data with each instruction by using the metadata mechanism; see this related question on how to set metadata.
However, if both your producer and consumer are passes, the standard way is to just have the producer pass store this data, and have the consumer pass ask the producer pass for it directly, using its methods. See this related documentation on how to set dependencies between passes.
You might also be interested in this other answer of mine, which talks a little more about this, and provides a code example for setting metadata.