[SCEV] Try to reuse existing value during SCEV expansion

Current SCEV expansion will expand SCEV as a sequence of operations

and doesn't utilize the value already existed. This will introduce

redundent computation which may not be cleaned up throughly by

following optimizations.

This patch introduces an ExprValueMap which is a map from SCEV to the

set of equal values with the same SCEV. When a SCEV is expanded, the

set of values is checked and reused whenever possible before generating

a sequence of operations.

The original commit triggered regressions in Polly tests. The regressions

exposed two problems which have been fixed in current version.

- Polly will generate a new function based on the old one. To generate an

instruction for the new function, it builds SCEV for the old instruction,

applies some tranformation on the SCEV generated, then expands the transformed

SCEV and insert the expanded value into new function. Because SCEV expansion

may reuse value cached in ExprValueMap, the value in old function may be

inserted into new function, which is wrong.

In SCEVExpander::expand, there is a logic to check the cached value to

be used should dominate the insertion point. However, for the above

case, the check always passes. That is because the insertion point is

in a new function, which is unreachable from the old function. However

for unreachable node, DominatorTreeBase::dominates thinks it will be

dominated by any other node.

The fix is to simply add a check that the cached value to be used in

expansion should be in the same function as the insertion point instruction.

- When the SCEV is of scConstant type, expanding it directly is cheaper than

reusing a normal value cached. Although in the cached value set in ExprValueMap,

there is a Constant type value, but it is not easy to find it out -- the cached

Value set is not sorted according to the potential cost. Existing reuse logic

in SCEVExpander::expand simply chooses the first legal element from the cached

value set.

The fix is that when the SCEV is of scConstant type, don't try the reuse

logic. simply expand it.

Differential Revision: http://reviews.llvm.org/D12090

llvm-svn: 259736