Well... Maybe Melchior had begun work on his Red Knife, which, during the time leading up to the Ocean Palace incident, became the sword we know as Masamune?
Though, I've also heard some better ideas, like that Melchior threw the knife into the Machine in the original timeline, which makes sense out of desperation.
... I'm still not entirely sure how you turn a basic red knife into a fancy broadsword by throwing it into a hunk of metal, albeit magical metal, but, eh. Different strokes.