Intuitively it seems easier to build strong inference heuristics for CGRA than FPGA given the more constrained (limited?) degrees of design freedom.

I've always been wary of inference-based systems that target clocked logic. Most of them (especially the C-based ones) are not suited to produce efficient designs and usually require some heavy massaging of the original code to make the inference system happy.