That's well within the Court's powers. They created the mess, so it's not unreasonable for them to fix it. It's not as though Congress passed a law allowing software patents or something.
I think the problem, though, is in how 35 USC 101 (patentable subject matter) got unhinged from 102 & 103 (novelty / non-obviousness). So you could meet the novelty requirements with something that wasn't patentable subject matter at all.
Once the lawyers could pry them apart like that, they could pass 101's requirements by saying the software is running on a computer and pass 102 & 103 requirements by saying that the software is new, even if the hardware in the patent is a normal PC. If they reversed that old decision and said that you can only pass 102 & 103 with something that is patentable subject matter, the scheme would fall apart.
You will note that this is, in effect, exactly what the decision to treat the stuff that isn't patentable subject matter as part of the prior art accomplishes and that Parker v. Flook does precisely that. Meanwhile, with Diamond v. Diehr, they got considered separately and ultimately separated.