This is an archive of the discontinued LLVM Phabricator instance.

[MustExecute] Forward iterate over conditional branches
ClosedPublic

Authored by jdoerfert on Oct 13 2019, 11:34 PM.

Details

Summary

If a conditional branch is encountered we can try to find a join block
where the execution is known to continue. This means finding a suitable
block, e.g., the immediate post dominator of the conditional branch, and
proofing control will always reach that block.

This patch implements different techniques that work with and without
provided analysis.

Diff Detail

Event Timeline

jdoerfert created this revision.Oct 13 2019, 11:34 PM
Herald added a project: Restricted Project. · View Herald TranscriptOct 13 2019, 11:34 PM
uenoku added a comment.EditedOct 15 2019, 9:40 AM

Basically it looks good to me.
I think we need a test for a loop(never-endless + propagation from exit block).
Something like,

;int g(int*);
;void h(int*);
;
;int f(int *u, int n){
;  for(int i = 0;i<n;i++){
;    h(u);
;  }
;  return g(nonnull u);
;}

define i32 @f(i32* %a, i32 %b) local_unnamed_addr {
  %3 = icmp eq i32 %b, 0
  br i1 %3, label %4, label %6

; <label>:4:                                      ; preds = %6, %2
  %5 = tail call i32 @g(i32* nonnull %a)
  ret i32 %5

; <label>:6:                                      ; preds = %2, %6
  %7 = phi i32 [ %8, %6 ], [ 0, %2 ]
  tail call void @h(i32* %a)
  %8 = add nuw i32 %7, 1
  %9 = icmp eq i32 %8, %b
  br i1 %9, label %4, label %6
}

declare void @h(i32*) willreturn nounwind 
declare i32 @g(i32*) willreturn nounwind

I'll add that test (in MustExecute and in the Attributor tests) but it will not be deduced yet. We need better loop support first.

Do I assume correctly that this is accepted with this additional test?

uenoku accepted this revision.Oct 29 2019, 12:05 PM

Do I assume correctly that this is accepted with this additional test?

Yes

This revision is now accepted and ready to land.Oct 29 2019, 12:05 PM
This revision was automatically updated to reflect the committed changes.