Freedom of movement grants the following:
spells and other magical effects can neither reduce the target's speed nor cause the target to be paralyzed or restrained. (PHB 244)
The petrifying gaze of a Basilisk says that:
On a failed save, the creature magically begins to turn to stone and is restrained. (MM 24)
Does the spell prevent the gaze from taking hold entirely? Or does it only allow you to move around while getting petrified?