It seems you've got the discography rule taken care of. You can generate the rewrite rules for all of your single post types via the rewrite
argument when your post types are registered. This may require you to manually register your post types, not sure what level of control that plugin provides. You'll also have to be careful about exactly what order you register the post types in so that your rules cascade from most to least specific. This may be another reason you'll have to manually register your post types.
Artists is the most simple, that will be just:
rewrite => array( 'slug' => 'artists' )
An album would be:
rewrite => array( 'slug' => 'artists/%artist%/discography' )
Lastly, songs would be:
rewrite => array( 'slug' => 'artists/%artist%/discography/%album%' )
You'll then need a post_type_link
function which loads the related data and swaps it in place of the %artist%
and %album%
rewrite tags. I'm not sure how those relationships are stored, so I can't tell you how that will work. You can see a similar example of this function with a taxonomy term on this answerthis answer.