Free Xilinx PicoBlaze Microcontroller Expands Support to Virtex-II Series FPGAs and CoolRunner-II CPLDs. PicoBlaze User Resources.
Regarding PicoBlaze for CPLDs, e.g. CoolRunner-II, lacking any on-chip block RAM instruction memory, the PB for CR2 requires you provide an external 16-bit wide instruction RAM. This may prove prove prohibitive in board area and cost. You can reduce the requirement to 8-bit external memory using a few more macrocells, of course, but in my opinion this application is a better fit for a device with embedded block memory (e.g. Spartan-IIE, etc.).
This does illustrate the utility and value of a modest amount of embedded RAM and/or FLASH in these larger CPLDs — an idea whose time has come.