What are barriers to Genetic Programming with cyclic graphs
Perhaps one reason is that constraints (perhaps somewhat arbitrary ones) would have to be imposed on what it means to interpret a program represented in this fashion.

However, recent work with CGP has actually explored the addition of cycles:
Recurrent CGP