Change Details

This patch currently isn't ready to commit, but posting it as a possible alternative approach to D44160. Currently we only look at the incoming values to a PHI node to determine if it actually only has one possible value, but actually we should be looking at the entire graph rooted at that node as this lets us handle more cases. This is specifically being done in order to improve alias analysis within GVN, as alias analysis uses GetUnderlyingObject which uses SimplifyInstruction, and GVN introduces phi graphs that SimplifyInstruction currently can't simplify (or rather, it can only handle them by iteratively simplifying each individual PHI node). This patch currently has several test failures LLVM :: CodeGen/AMDGPU/nested-loop-conditions.ll LLVM :: CodeGen/PowerPC/expand-contiguous-isel.ll LLVM :: CodeGen/X86/ragreedy-hoist-spill.ll LLVM :: Transforms/CodeGenPrepare/X86/sink-addrmode-base.ll LLVM :: Transforms/CodeGenPrepare/X86/sink-addrmode-two-phi.ll LLVM :: Transforms/IndVarSimplify/2011-11-17-selfphi.ll LLVM :: Transforms/IndVarSimplify/no-iv-rewrite.ll Some of these are tests that use phi nodes in too simple a way that now gets optimised away (as are several tests that this patch adjusts) but the IndVarSimplify failures are much harder to resolve. What's happening is: * LoopSimplify calls SimplifyInstruction only on PHI nodes in the loop header * Currently this does nothing in these tests, but now we eliminate the PHI but that leaves an unsimplified PHI node in the loop body * IndVarSimplify now does nothing because it sees no induction variable * So we are left with the unsimplified PHI that we didn't previously have I'm not sure how to fix this. Making LoopSimplify simplify all of the PHI nodes in the loop fixes this test failure, but causes ~20 more.

Currently in aliasPHI we give up if we have a PHI as an incoming value to a PHI, to avoid having O(m x n) calls to aliasCheck. This patch relaxes that slightly to allow looking through PHIs if we only end up with one value as a result. This should be fine, as in the worst case we look through n blocks to find this single value, then look through n blocks again if the value we're comparing against is also a PHI, giving O(n) where n is bounded by MaxLookupSearchDepth which we already allow GetUnderlyingObject to do. This is specifically being done in order to improve alias analysis within GVN, as GVN can introduce PHI graphs of this kind where there's only one underlying value.

This patch currently isn't ready to commitCurrently in aliasPHI we give up if we have a PHI as an incoming value to a PHI, to avoid having O(m x n) calls to aliasCheck. This patch relaxes that slightly to allow looking through PHIs if we only end up with one value as a result. This should be fine, as in the worst case we look through n blocks to find this single value, then look through n blocks again if the value we're comparing against is also a PHI, but posting it as a possible alternative approach to D44160giving O(n) where n is bounded by MaxLookupSearchDepth which we already allow GetUnderlyingObject to do. Currently we only look at the incoming values to a PHI node to determine if it actually only has one possible value, but actually we should be looking at the entire graph rooted at that node as this lets us handle more cases. This is specifically being done in order to improve alias analysis within GVN, as alias analysis uses GetUnderlyingObject which uses SimplifyInstruction, and GVN introduces phi graphs that SimplifyInstruction currently can't simplify (or rather, it can only handle them by iteratively simplifying each individual PHI node). This patch currently has several test failures LLVM :: CodeGen/AMDGPU/nested-loop-conditions.ll LLVM :: CodeGen/PowerPC/expand-contiguous-isel.ll LLVM :: CodeGen/X86/ragreedy-hoist-spill.ll LLVM :: Transforms/CodeGenPrepare/X86/sink-addrmode-base.ll LLVM :: Transforms/CodeGenPrepare/X86/sink-addrmode-two-phi.ll LLVM :: Transforms/IndVarSimplify/2011-11-17-selfphi.ll LLVM :: Transforms/IndVarSimplify/no-iv-rewrite.ll Some of these are tests that use phi nodes in too simple a way that now gets optimised away (as are several tests that this patch adjusts) but the IndVarSimplify failures are much harder to resolve. What's happening is: * LoopSimplify calls SimplifyInstruction only on PHI nodes in the loop header * Currently this does nothing in these tests, but now we eliminate the PHI but that leaves an unsimplified PHI node in the loop body * IndVarSimplify now does nothing because it sees no induction variable * So we are left with the unsimplified PHI that we didn't previously haveas GVN can introduce PHI graphs of this kind where there's only one underlying value. I'm not sure how to fix this. Making LoopSimplify simplify all of the PHI nodes in the loop fixes this test failure, but causes ~20 more.