This is an archive of the discontinued LLVM Phabricator instance.

[SimpleLoopUnswitch] Fix introduction of UB when hoisted condition may be undef or poison
ClosedPublic

Authored by aqjune on Jan 23 2017, 3:58 AM.

Details

Summary

Loop unswitch hoists branches on loop-invariant conditions. However, if this
condition is poison/undef and the branch wasn't originally reachable, loop
unswitch introduces UB (since the optimized code will branch on poison/undef and
the original one didn't)).
We fix this problem by freezing the condition to ensure we don't introduce UB.

We will now transform the following:

while (...) {
  if (C) { A }
  else   { B }
}

Into:

C' = freeze(C)
if (C') {
  while (...) { A }
} else {
  while (...) { B }
}

This patch fixes the root cause of the following bug reports (which use the old loop unswitch, but can be reproduced with minor changes in the code and -enable-nontrivial-unswitch):

Diff Detail

Event Timeline

aqjune created this revision.Jan 23 2017, 3:58 AM
nlopes edited the summary of this revision. (Show Details)Jan 23 2017, 3:59 AM
nlopes added a subscriber: nlopes.Jan 24 2017, 1:07 AM
regehr added a subscriber: regehr.Jan 28 2017, 10:03 PM
aqjune updated this revision to Diff 86252.Jan 30 2017, 12:13 AM
filcab added a subscriber: filcab.Feb 2 2017, 9:49 AM

Is NeedFreeze always true? If so, why have the parameter?
If not, when is it not?

include/llvm/IR/IRBuilder.h
1718 ↗(On Diff #86252)

Maybe add

if (isa<FreezeInst>(Arg))
  return Arg;

so we don't need to create a FreezeInst that will be immediately simplified in the next run of instsimplify (and avoids ReplaceAllUsesWith)?
Unless I missed something.

1734 ↗(On Diff #86252)

What happens if we try to Freeze a non-Instruction, non-Argument Value subclass (any type of Constant?)?
From the name and location, I'm assuming this function should be fairly generic.

lib/Transforms/Scalar/LoopUnswitch.cpp
243

Why is it a default parameter here?

aqjune added inline comments.Feb 2 2017, 4:46 PM
include/llvm/IR/IRBuilder.h
1718 ↗(On Diff #86252)

@filcab I think it is caller's job to check whether the value is simple enough and creating a new freeze is unnecessary. A function FreezeBranchCondition in this patch (which is in LoopUnswitch.cpp) does similar thing : first of all it checks whether the new freeze instruction is needed (by calling isGuaranteedNotToBeUndefOrPoison), and then calls this function (CreateFreezeAtDef).

aqjune added a comment.Feb 2 2017, 8:37 PM

NeedFreeze is set to true in this patch, but it can have different value in upcoming patch (https://reviews.llvm.org/D29016).

aqjune updated this revision to Diff 106917.Jul 17 2017, 12:17 PM

Rebased to svn commit 308173

reames requested changes to this revision.Nov 8 2019, 7:37 AM

p.s. You know you're changing the old pass which isn't used in the new pass manager right? You may instead wish to focus on SimpleLoopUnswitch which is the new version.

include/llvm/IR/IRBuilder.h
1795 ↗(On Diff #106917)

This is really not idiomatic for an IRBuilder function. The standard idioms is to just insert the requested instruction sequence at the specified insertion point. Please refactor to match that idiom and move other logic to caller or utility outside of IRBuilder.

lib/Transforms/Scalar/LoopUnswitch.cpp
243

Please leave this out of the current patch. It belongs in the one using the must execute logic.

I'd be open to combining them if you thought that was needed.

823

I think this can and should be simpler. If we need a freeze, just insert it into the end of the preheader. The complexity of hoisting to def doesn't seem warranted.

This revision now requires changes to proceed.Nov 8 2019, 7:37 AM
aqjune updated this revision to Diff 242267.Feb 4 2020, 12:36 AM
  • Target SimpleLoopUnswitch to fix introduction of UB
  • Use ICFLoopSafetyInfo::isGuaranteedToExecute to not freeze condition if hoisted branch is guaranteed to be reachable

The second change was necessary to minimize the updates at unit tests.
(which was https://reviews.llvm.org/D29016 , but it needed only small amount of change so I moved it to here)

Herald added a project: Restricted Project. · View Herald TranscriptFeb 4 2020, 12:36 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
aqjune marked 3 inline comments as done.Feb 4 2020, 12:39 AM
reames accepted this revision.Feb 25 2020, 9:43 AM

LGTM

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
2179 ↗(On Diff #242267)

As a further enhancement (separate change), I think you can improve the logic for this case slightly. If you can prove that the original condition would have triggered UB if any of the invariant components had been poison, then you can avoid the freeze on the partially unswitched condition.

This revision is now accepted and ready to land.Feb 25 2020, 9:43 AM
aqjune retitled this revision from [LoopUnswitch] Fix introduction of UB when hoisted condition may be undef or poison to [SimpleLoopUnswitch] Fix introduction of UB when hoisted condition may be undef or poison.Feb 25 2020, 8:44 PM
aqjune edited the summary of this revision. (Show Details)
This revision was automatically updated to reflect the committed changes.
aqjune marked an inline comment as done.Feb 25 2020, 9:20 PM
aqjune added inline comments.
llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
2179 ↗(On Diff #242267)

IIUC, it is addressed by this patch because we could exploit that branching on poison is UB:

// want to partial unswitch cond2
for (..)
  if (cond1 && cond2) { A } else { B } // if cond2 is poison, cond1 && cond2 is also poison, so this is UB
=>
if (cond2) // freeze is not needed here
  for (..) { if (cond1) { A } }
else
  for (..) { B }
aqjune marked an inline comment as done.Feb 25 2020, 9:49 PM
aqjune added inline comments.
llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
2179 ↗(On Diff #242267)

(to clarify, it is assumed in the example that if(cond1 && cond2) is guaranteed to execute, meaning that there is no intervening branch or function call that may not return between the if statement and loop preheader )

Thx for the patch!

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
186 ↗(On Diff #246622)

Nit: InsertFreze

aqjune marked 2 inline comments as done.Feb 25 2020, 10:34 PM
aqjune added inline comments.
llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
186 ↗(On Diff #246622)
aqjune marked an inline comment as done.Feb 27 2020, 6:17 PM

Reverted due to performance reason (https://github.com/llvm/llvm-project/commit/2b5a8976514de326bb84f0913d9d451089c11d22 ) ; LICM/CSE support for freeze is needed

Now we have a pass for removing freezes in a loop (D77524). I can check whether the existing slowdowns can be addressed with it. I'll be a bit busy for a month, so it may proceed a bit slowly.
BTW, having an attribute for function arguments that states the value is already frozen will be really helpful for reducing the amount of introduced freezes (not only for loop unswitch, but also for other transformations that need freeze operations). I remember that it was called nonpoison in the previous llvm-dev discussion.
According to C/C++ standard, if indeterminate value is produced by an evaluation, the behavior is undefined except when the value was a family of char type:
C++14: https://timsong-cpp.github.io/cppwp/n4140/dcl.init#12
C++17: https://timsong-cpp.github.io/cppwp/n4659/dcl.init#12
C++11: https://timsong-cpp.github.io/cppwp/n3337/conv.lval#1 (wording is a bit different)
C11: https://port70.net/~nsz/c/c11/n1570.html#6.3.2.1p2
This means that it is valid to put the attribute unless the type is char or an aggregate with char when translating C/C++ to IR.
What do you think? @jdoerfert @reames This will help support other optimizations, such as supporting hoisting divisions from a loop when its divisor is a non-zero value derived from a function argument.