Currently most of my changes are in analyzejoin.c, but I did also have to make changes to load the foreign key constraints so that they were available to the planner. One thing that is currently lacking, which would likely be needed, before the finished patch is ready, would be a "relhasfkeys" column in pg_class. Such a column would mean that it would be possible to skip scanning pg_constraint for foreign keys when there's none to find. I'll delay implementing that until I get a bit more feedback to weather this patch would be a welcome addition to the existing join removal code or not.
I've modified this patch to include a new "relhasfkey" column in pg_class, and then only attempt to load the foreign keys in get_relation_info() if the pg_class flag is true.
Currently what I'm not quite sure on is the best place to be clearing this flag. I see that relhaspkey is cleared during vacuum, but only if there's no indexes at all on the relation. It seems that it will remain set to "true" after vacuum, if the primary key is dropped and there's still other indexes on the relation. My guess here is that this is done so that pg_constraint does not have to be checked to see if a PK exists, which is why I'm not sure if this would be the correct place for me to do the same in order to determine if there's any FKs on the relation. Though I can't quite think where else I might clear this flag.