I think the question was "how did the phone company know the location", and GPS may be part of the answer.

In the US, E911 requires all phones to be able to report their physical location. Phone companies may use this ability to respond to police location requests. I don't know one way or another, but it seems likely.

Do phone companies have access to that when the phone isn't actively placing a 911 call?

Even if they don’t, they can use trilateration/triangulation (for which I assume they always have the necessary information: signal strength and approximate distance) to pinpoint the exact location.

Good question. Big picture, the phone companies have access to that information any time they want.

The E911 laws, though, only require that the location information be obtained and forwarded when the call is placed.

So, I don't know. I don't know anything beyond that.