This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] fold zexts and constants into a phi (PR24766)
ClosedPublic

Authored by spatel on Sep 14 2015, 3:54 PM.

Details

Summary

This is one step towards solving PR24766:
https://llvm.org/bugs/show_bug.cgi?id=24766

We were not producing the same IR for these two C functions because the store to the temp bool causes extra zexts:

#include <stdbool.h>

bool switchy(char x1, char x2, char condition) {
   bool conditionMet = false;
   switch (condition) {
   case 0: conditionMet = (x1 == x2); break;
   case 1: conditionMet = (x1 <= x2); break;
   }
   return conditionMet;
}

bool switchy2(char x1, char x2, char condition) {
   switch (condition) {
   case 0: return (x1 == x2);
   case 1: return (x1 <= x2);
   }
  return false;
}

As noted in the code comments, this test case manages to avoid the more general existing phi optimizations where there are only 2 phi inputs or where there are no constant phi args mixed in with the casts ops. It seems like a corner case, but if we don't catch it, then I don't think we can get SimplifyCFG to further optimize towards the canonical form for this function shown in the bug report.

Diff Detail

Repository
rL LLVM

Event Timeline

spatel updated this revision to Diff 34747.Sep 14 2015, 3:54 PM
spatel retitled this revision from to [InstCombine] fold zexts and constants into a phi (PR24766).
spatel updated this object.
spatel added reviewers: nicholas, hfinkel, majnemer.
spatel added a subscriber: llvm-commits.
sanjoy added a subscriber: sanjoy.Sep 15 2015, 7:29 PM
sanjoy added inline comments.
lib/Transforms/InstCombine/InstCombinePHI.cpp
399 ↗(On Diff #34747)

When will Cast->getOpcode() != FirstCast->getOpcode()? Doesn't Cast->getOpcode() always have to be Instruction::ZExt?

416 ↗(On Diff #34747)

I'd structure this slightly different -- I'd have

SmallVector<Value *, 4> NewIncoming;
Type *NarrowType = nullptr;  // to keep track of what you're zext'ing from is same for all inputs

for (Value *V : Phi.incoming_value()) {
   // Check V here, and either append to NewIncoming or
   // return nullptr if you see something you cannot handle
   // (including constants)
}

// Create new PHI node with all the incoming values in NewIncoming

That'll keep most of the interesting logic in this function in one place.

spatel added inline comments.Sep 16 2015, 7:57 AM
lib/Transforms/InstCombine/InstCombinePHI.cpp
399 ↗(On Diff #34747)

Hi Sanjoy - thanks for looking at this!
Yes, this check is unnecessary. This and the code structure (and the variable names and comments) are more general than they need to be because I started off hoping to handle any cast type. Let me make everything zext-specific for this patch, and then we can generalize it later if needed.

spatel updated this revision to Diff 34908.Sep 16 2015, 11:21 AM

Patch updated based on Sanjoy's feedback:

  1. Reorganize code so all interesting logic is in one loop.
  2. Remove unnecessary opcode check because we're only dealing with zexts.
  3. Fix variable names and comments to match the fact that we're only dealing with zexts.
hfinkel added inline comments.Sep 22 2015, 3:58 PM
lib/Transforms/InstCombine/InstCombinePHI.cpp
437 ↗(On Diff #34908)

Do we already have a regression test that covers these cases?

test/Transforms/InstCombine/phi.ll
662 ↗(On Diff #34908)

Could you please actually check that the PHI itself is formed correctly, and add a test case that covers the handling of the truncated-constant incoming value?

spatel marked 2 inline comments as done.Sep 24 2015, 8:38 AM
spatel added inline comments.
lib/Transforms/InstCombine/InstCombinePHI.cpp
437 ↗(On Diff #34908)

There are other tests that cover the basics here:
a. test6 ("Suck casts into phi")
b. test13 has a case with a constant in a phi

...but I think we should have tests for phis that include more than 2 operands, so I've added those to show that the existing functions are working as expected on the constructs that this new code doesn't cover.

test/Transforms/InstCombine/phi.ll
662 ↗(On Diff #34908)

Yes - that was just lazy.
Let me know if the new test cases with 0/1 -> false/true cover the constant scenario you're thinking of.

spatel updated this revision to Diff 35632.Sep 24 2015, 8:41 AM

Patch updated:

  1. Add tests to show that existing optimizations are working on cases not handled by this new code.
  2. Add test with 2 constants and 2 variables to show that constant shrinking is working in the new code.
hfinkel accepted this revision.Sep 25 2015, 2:37 PM
hfinkel edited edge metadata.

LGTM.

This revision is now accepted and ready to land.Sep 25 2015, 2:37 PM
This revision was automatically updated to reflect the committed changes.