the entire map, Mordor included is the North and West of Middle Earth. Hence 'Westron' is in fact the common language of everyone there. You have dialects, of course.

The Faithful and their allies generally kept an antique version of it, seeing how bonded they were to the Elvish languages and considered Adunaic to be the tongue of the unlearned.

The more southern settlements like Umbar were governed by the King's Men and Black Numenoreans, whose linguistic preference was Adunaic, the language of the sailors. They admitted Men of Harad into their settlements, which means that any new development comes from Haradic words. Gondor took plenty from the Northmen and later the Rohirrim, but gave more to the Rohirrim until they spoke in similar tones. Thengel's stay in Gondor further made sure that the Gondor dialect of it was spoken in the Mark.

The Haradrim did deal with Gondor once upon a time, perhaps even sailing to Pelargir to trade. If you have pirates, you must have trade ships too (who are you gonna rob?). As Adunaic was the tongue of the sailors, it's no surprise if a captain of the South spoke Westron if only in a dialect.

The Easterlings literally do come form the East, but possibly trade with the Iron Hills and Dale, and Erebor. The Dwarves do have four Houses based in the East, so there may be some Khuzdul in Easterling tongues,as it was with the Easterlings of the First Age. The Dwarf-knowledge we have is from Gimli, a Longbeard; some rules may not apply to other Houses.

There is but one task remaining in Arda-we,the Dragons of Valinor will make it happen.

Lone resident of the Republic of Gondor

PO-TA-TOE-S not PO -TAH-TOE-S!