Page MenuHomePhabricator

[LoopUnswitch] Fix introduction of UB when hoisted condition may be undef or poison
Needs RevisionPublic

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 at least the following bug reports:

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
1798

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.

1814

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
229

Why is it a default parameter here?

aqjune added inline comments.Feb 2 2017, 4:46 PM
include/llvm/IR/IRBuilder.h
1798

@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

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
229

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.

897

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