SCEV produces two objects for identical inputs

[Quuxplusone]

Bugzilla Link	PR11052
Status	NEW
Importance	P normal
Reported by	Nick Lewycky (nicholas@mxc.ca)
Reported on	2011-10-02 18:04:11 -0700
Last modified on	2017-09-10 10:18:11 -0700
Version	trunk
Hardware	PC Linux
CC	atrick@apple.com, florian_hahn@apple.com, llvm-bugs@lists.llvm.org
Fixed by commit(s)
Attachments	scev-testcase.patch (2035 bytes, text/plain)
Blocks
Blocked by
See also

Created attachment 7389
testcase

A unittest is attached, but the short story is that this:

  SmallVector<const SCEV *, 4> Sum;
  Sum.push_back(SE.getMulExpr(Arg1, Arg2));
  Sum.push_back(SE.getMulExpr(Arg3, Arg2));
  Sum.push_back(SE.getMulExpr(Arg1, Arg4));
  const SCEV *LHS = SE.getAddExpr(Sum);

  const SCEV *RHS = SE.getMulExpr(Arg1, Arg2);
  RHS = SE.getAddExpr(RHS, SE.getMulExpr(Arg3, Arg2));
  RHS = SE.getAddExpr(RHS, SE.getMulExpr(Arg1, Arg4));

produces two different SCEVs:

  LHS: (((%1 + %3) * %0) + (%1 * %2))
  RHS: (((%0 + %2) * %1) + (%0 * %3))

In particular note how everything is in the same order, all 3 MulExpr's are the
same inputs, and they're used in the same order.

[Quuxplusone]

Attached scev-testcase.patch (2035 bytes, text/plain): testcase

[Quuxplusone]

I'm not sure this problem is realistically avoidable in general. Maybe we could handle more patterns. However, it would be reasonable to implement a true equivalence checker that could run with assertions/verification enabled.