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?
The spell essentially makes you immune to the restrained condition (from magical effects). You would not be restrained by the gaze but would still have to make saving throws against turning to stone.
It must repeat the saving throw at the end of its next turn. On a success, the effect ends. On a failure, the creature is petrified until freed by the greater restoration spell or other magic.
Basically, you treat each effect of something as it's own unless it is otherwise clarified in the text. This question covers a similar issue.
