Violent crime in Portugal has been rising steadily. Even if it had simply held steady after decriminalization (which seems not to be the case), that would still refute the idea that legalization is a good way to stanch the rate of incarceration.
Alas, it gets complicated to isolate variables when you consider the whole economic meltdown they're experiencing. Public policy is hard, let's go programming!