Compilation of complex match expressions - Quadratic explosion possible?

I'm in the process of developing a variety of intentions and inspections for
IntelliJ IDEA's Scala support, and ran across an interesting issue. For
several desirable code transformations, it is necessary to be able to
calculate whether two Scala expressions have equivalent parse trees, up to
some simple transformations. I've been using Scala's pattern matching
extensively in this project, and have created a large set of extractors to
allow convenient matching against the JetBrains Scala AST, so I naturally
turned to it for this problem. My first cut looked something like

def isEquivalent(exp1: ScExpression, exp2: ScExpression): Boolean =
(exp1, exp2) match {
case (literal1: ScLiteral, literal2: ScLiteral) => literal1.getText ==
literal2.getText
case (InfixExpr(lhs1, op1, rhs1), InfixExpr(lhs2, op2, rhs2)) => op1
== op2 && isEquivalent(lhs1, lhs2) && isEquivalent(rhs1, rhs2)
case (PrefixExpr(op1, operand1), PrefixExpr(op2, operand2)) => op1 ==
op2 && isEquivalent(operand1, operand2)
case (PostfixExpr(op1, operand1), PostfixExpr(op2, operand2)) => op1
== op2 && isEquivalent(operand1, operand2)
case (Return(None), Return(None)) => true
case (Return(Some(val1)), Return(Some(val2))) => isEquivalent(val1,
val2)
case (Throw(val1), Throw(val2)) => isEquivalent(val1, val2)
case (While(cond1, body1), While(cond2, body2)) => isEquivalent(cond1,
cond2) && isEquivalent(body1, body2)
case (Do(cond1, body1), Do(cond2, body2)) => isEquivalent(cond1,
cond2) && isEquivalent(body1, body2)
case (Tuple(ops1), Tuple(ops2)) => ops1.length== ops2.length &&
ops1.equalsWith(ops2, isEquivalent(_, _))
case (Block(ops1), Block(ops2)) => ops1.length== ops2.length &&
ops1.equalsWith(ops2, isEquivalent(_, _))
case _ => false
}

This worked fine, but as I added more cases, the compilation got slower and
slower, and eventually when it got to the size shown would simply fail to
compile, with some cryptic error message that indicated that some method had
gotten too long. It seems as though this sort of pattern matching against
pairs of extractors engenders some odd quadratic behaviour. (It doesn't seem
to have anything to do with tail recursion, as it still occurs if I recode
it with a debugging println after the match.) I've rewritten the
equivalence checker to use nested match expressions instead, and the problem
goes away, but I was looking for some insight as to why this might have
occured. Any pointers to the mechanics of compilation of match expressions
would be geatly appreciated. Ideally, I would then take those insights,
automate them, and have IDEA tell me when matches were getting problematic.

And as an aside, I'll take this opportunity to say that Scala extractors
aren't better than sex, but sliced bread is pretty worried. I realize they
probably aren't all that interesting from a type-theoretic standpoint, but
from a business point of view, it means I get to pitch Scala by saying "And
using this feature, you can code up pretty much any of your common business
rules in a way that is clear, concise, nestable, cascadable, reusable, and
independent of the underlying data structure. Oh, and it also works with
XML. Now let me show you for-comprehensions, which lets you do the same for
your looping logic..." That code sample above is about 10% of the size of
the equivalent Java, and vastly more likely to be correct the moment it is
written (or would be, um, if it compiled). Good work.