Page MenuHomePhabricator

[LICM] Support hosting of dynamic allocas out of loops

Authored by reames on Oct 20 2019, 4:19 PM.



This patch implements a correct, but not terribly useful, transform. In particular, if we have a dynamic alloca in a loop which is guaranteed to execute, and provably not captured, we hoist the alloca out of the loop. The capture tracking is needed so that we can prove that each previous stack region dies before the next one is allocated. The transform decreases the amount of stack allocation needed by a linear factor (e.g. the iteration count of the loop).

Now, I really hope no one is actually using dynamic allocas. As such, why this patch?

Well, the actual problem I'm hoping to make progress on is allocation hoisting. There's a large draft patch out for review (, and this patch was the smallest chunk of testable functionality I could come up with which takes a step vaguely in that direction.

Once this is in, it makes motivating the changes to capture tracking mentioned in TODOs testable. After that, I hope to extend this to trivial malloc free regions (i.e. free dominating all loop exits) and allocation functions for GCed languages.

Diff Detail

Event Timeline

reames created this revision.Oct 20 2019, 4:19 PM
Herald added a project: Restricted Project. · View Herald TranscriptOct 20 2019, 4:19 PM
apilipenko accepted this revision.Nov 7 2019, 4:21 PM
apilipenko added inline comments.
796–799 ↗(On Diff #225807)

This is even more restrictive. We can't let alloca be used in a phi, so this value can be observed in a different iteration.

  %iv = phi i64 [, %for.body ], [ 0, %entry ]
  %p = phi i64* [ %a, %for.body ], [ %x, %entry ]
  %a = alloca i64
  ; In the orginal program %p and %a point to different locations and don't alias
  ; If you hoist the alloca %p %a will point to the same memory location = add nuw nsw i64 %iv, 1
  %exitcond = icmp ult i64 %iv, %n
  br i1 %exitcond, label %for.body, label %exit

It would be nice to have a test like this.

This revision is now accepted and ready to land.Nov 7 2019, 4:21 PM
This revision was automatically updated to reflect the committed changes.