A design fits with no timing constraints placed on it. However, when I add timing constraints, the design no longer fits in the device.
The software is attempting to speed up your critical paths by flattening the logic; as a result of the wider fan-ins into each function block, the design expands to the point where it can no longer fit.
Try the following solutions:
1. Use the "speed" option when fitting your design.
2. Ensure that you have no macrocells in the critical path in low-power mode. (This applies only to the XC9500/XL/XV families.)
3. Try targeting a faster speed grade device.
4. Relax the timing constraints.