[InstCombine] Handle PHI nodes in PtrReplacer

[gandhi21299]

Summary

This patch adds on to the functionality implemented
in rG42ab5dc5a5dd6c79476104bdc921afa2a18559cf,
where PHI nodes are supported in the use-def traversal
algorithm to determine if an alloca ever overwritten
in addition to a memmove/memcpy. This patch implements
the support needed by the PointerReplacer to collect
all (indirect) users of the alloca in the case where a PHI
is involved. Finally, a new PHI is defined in the replace
method which takes in replaced incoming values and
updates the WorkMap accordingly.

[gandhi21299]

ping

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

63

Why do we care about default address space here? I think what you probably want to check is PHI->getType()->getPointerAddressSpace() != TheCopy->getPointerAddressSpace()? But also, this code assumes that TheCopy is available before the PHI is seen, and I don't think anything guarantees that -- order of uses is unpredictable. I think you'd want to perform the bailout in PointerReplacer::collectUsers() instead? Maybe I'm misunderstanding the purpose here.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

55

Why do we need the LastPHI variable? I'd have expected that just setting IsOffset=true is equivalent? (With a rename IsOffset -> ForbidCopy or something?)

[gandhi21299]

• Eliminated LastPHI as it had no valuable impact
• Removed the addrspace cast checks in isOnlyCopiedFromConstantMemory(..) as pointed out. Instead, determine if the alloca is directly used as an incoming value in a PHI while collecting users of an alloca in PointerReplacer::collectUsers(..). If the address spaces of the PHI and the destination of the Copy inst differ and there is a direct use of the alloca, an addrspace cast will be required to further allow the PHI for replacement. Since we do not allow for addrspace casts, reject the PHI at that moment.

[gandhi21299]

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

63

I implemented it for the function @addrspace_diff_keep_alloca in the test file. I improved upon the solution by moving the changes over to collectUsers() which does make a lot more sense wrt my previous solution. I hope it seems fine now.

[gandhi21299]

removed dbg statements

[arsenm]

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

116

I think I'm getting lost in the different revisions of the patch; not sure what this comment is referring to anymore. There isn't anything about phi handling right here?

271

Don't like auto for addrspace

[gandhi21299]

Use unsigned instead of auto

[gandhi21299]

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

116

I had a revision previously where I was tracking PHI nodes seperately, as opposed to IsOffset. I replaced it with my changes in PointerReplacer::collectUsers(..).

[gandhi21299]

Allow PHI nodes only if the number of incoming values is less than 5

[gandhi21299]

ping

[gandhi21299]

• PHI's need to be kept track of to avoid inserting them repeatedly into ValuesToInspect.

[gandhi21299]

• Applied clang-format and rebased

[gandhi21299]

• Insert PHI into ValuesToInspect only when it hasn't seen before. Otherwise, continue with the use-def traversal.

[gandhi21299]

ping

[gandhi21299]

@nikic Thanks for committing on my behalf, may I close this revision?

[nikic]

@gandhi21299 I only landed the basic isOnlyCopiedFromConstantMemory() support, but the PointerReplacer part is still open. I'm think the logic there is still not quite correct -- will take another look tomorrow.

[nikic]

Rebased patch over committed changes: https://gist.github.com/nikic/ce69a66fdc0985d1af7a56bf024bc860

With additional tests added (in particular @addrspace_diff_keep_alloca_extra_gep) the patch causes an assertion failure.

You are currently going over phi operands and checking whether one of them is the memcpy dest, but I'm not sure what this check is intended to achieve, semantically. I think it just works by accident on existing test cases.

The problem is that we need a closed graph to perform the pointer replacement (can't have any external inputs) and additionally the worklist also needs to be ordered correctly, so that inputs are always replaced before the using instruction. The former is a hard requirement for this to work, the latter is a requirement of the current algorithm.

If you don't want to change the current replacement approach, then I think a good way to enforce this would be to do the following: When processing a phi node, check whether all phi operands are already in the worklist. If not, don't visit the phi yet (wait until everything is in the worklist). Add the phi to some extra set, and after collectUsers(), check that all phis are in the worklist. This is to handle the case where an input was not part of the graph and the phi is never added to the worklist.

[gandhi21299]

• Revised PointerReplacer::collectUsers(..) as requested.
• Passes all tests under check-llvm-transforms, including replace-alloca-phi.ll

[gandhi21299]

• Rebased and removed an irrelevant comment.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

291

I don't think you need this check (and as such this whole loop can be dropped).

304

I think this should only be done after the whole collectUsers() phase, currently you do it on each recursive call.

[gandhi21299]

• Eliminated the redundant loop as pointed out by reviewer
• Created a new method that drives the recursive algorithm for collecting users, this was necessary to avoid publicizing the member variables of PointerReplacer.

[gandhi21299]

• clang-format

[nikic]

Logic looks correct to me now. Looks like the test changes got lost though?

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

15

Shouldn't be needed (already used in file).

249

Copy argument no longer needed

270

Could make ValuesToRevisit use Instruction * rather than Value * and save this cast.

284

Can use any_of instead of for here and avoid the ValueInserted variable.

[gandhi21299]

In D136201#4052834, @nikic wrote:

Logic looks correct to me now. Looks like the test changes got lost though?

I rebased the changes and there weren't any test changes in the reduced version of this patch.

[gandhi21299]

• Changes as requested by reviewer, updated tests accordingly

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

271

Drop llvm:: prefix.

278

Missing the insertion into ValuesToRevisit here?

[gandhi21299]

• Replaced calls from collectUsers to collectUsersRecursive, which now generates the code we expect for @loop_phi_remove_alloca and @loop_phi_late_memtransfer_remove_alloca.

[gandhi21299]

• removed #include "STLExtras.h"

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

55

Spurious change.

278–284

The ValuesToRevisit update should happen outside the any_of.

438

Spurious change.

llvm/test/Transforms/InstCombine/replace-alloca-phi.ll

11

Broken check line (should be CHECK).

[gandhi21299]

• changes as suggested by reviewer

[nikic]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

278

Unneeded Inst capture.

279

Spurious change

[gandhi21299]

• requested updates

Thanks a bunch for such in-depth review, I will commit this patch.