Page MenuHomePhabricator

[LICM] Support of widenable condition guards in LICM
Needs RevisionPublic

Authored by mkazantsev on Feb 14 2019, 4:51 AM.

Details

Summary

LICM can hoist intrinsic guards. This patch teaches it hoist widenable condition guards as well.

Diff Detail

Event Timeline

mkazantsev created this revision.Feb 14 2019, 4:51 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 14 2019, 4:51 AM
mkazantsev planned changes to this revision.Feb 14 2019, 9:26 PM
mkazantsev retitled this revision from [WIP] Support of widenable condition guards in LICM to [LICM] Support of widenable condition guards in LICM.

LGTM, but I would like to have somebody else to take a look at this as well...

llvm/lib/Transforms/Scalar/LICM.cpp
87

Since these are very special branches, can you word it as "Number of widenable branches hoisted", pls?

This looks to be a form of unswitching. Can you explain why this needs to be done in LICM rather than in unswitching?

The main motivation is unification - I don't want to leave a single thing that is supported for intrinsic guards and not supported for control flow guards. Unswitching has known problems related to exponential code size growth, so I don't want our ability to eliminate guards in loops to depend on its cost model.

The main motivation is unification - I don't want to leave a single thing that is supported for intrinsic guards and not supported for control flow guards. Unswitching has known problems related to exponential code size growth, so I don't want our ability to eliminate guards in loops to depend on its cost model.

Trivial unswitch does not have a problem of exponential code growth.
Basically, what you do here does match what trivial unswitch does.
So in order to rely on unswitch we just need to ensure that this widenable branch thing does fall into a trivial unswitch category.

Ok. Then I suggest to hold it off unless we see a case where unswitch doesn't do its job and this does.

Does the existing code successfully hoist the widenable_condition call itself out of the loop? If not, splitting out specifically that part of the transform would be well called for and necessary for unswitch to make progress. If it does, then the patch as written includes redundant handling which should be removed.

reames requested changes to this revision.Feb 20 2019, 8:54 AM
This revision now requires changes to proceed.Feb 20 2019, 8:54 AM

Does the existing code successfully hoist the widenable_condition call itself out of the loop? If not, splitting out specifically that part of the transform would be well called for and necessary for unswitch to make progress. If it does, then the patch as written includes redundant handling which should be removed.

Current trunk can not hoist this widenable call.
Hence it makes sense to modify this fix so it hoists the call itself (and perhaps the rest of condition) but keeps the branch unmodified, for unswitch later to finish the task.

FWIW, I looked briefly at the first test, and this could be addressed with enabling MemorySSA.

  1. We don't look carefully at Calls in canSinkOrHoist. The same handling that I added on the branch for store instructions, can be used for call instructions (i.e. no clobbering definitions and no interfering uses). With this change I see @llvm.experimental.widenable.condition() is hoisted.
  2. The load is still not hoisted, due to failing the condition isSafeToExecuteUnconditionally, but it is optimized to ; MemoryUse(liveOnEntry). But new unswitch seems to pick it up afterwards, the load is hoisted to entry.split with bin/opt -enable-mssa-loop-dependency=true -basicaa -licm -simple-loop-unswitch.

This may not be the immediate solution you're looking for, but I hope this will become the preferred alternative reasonably soon.

Clarification: the condition gets hoisted as well once the call gets hoisted.

LICM hoisting to entry:   %widenable_cond = call i1 @llvm.experimental.widenable.condition()
LICM hoisting to entry:   %exiplicit_guard_cond = and i1 %cond, %widenable_cond