This is an archive of the discontinued LLVM Phabricator instance.

[IR][TRE] Support associative intrinsics
Needs ReviewPublic

Authored by caojoshua on May 14 2023, 10:33 PM.

Details

Summary

There is support for intrinsics in Instruction::isCommunative, but there
is no equivalent implementation for isAssociative. This patch builds
support for associative intrinsics with TRE is an application. TRE can
now have associative intrinsics as an accumulator. For example:

struct Node {
  Node *next;
  unsigned val;
}

unsigned maxval(struct Node *n) {
  if (!n) return 0;
  return std::max(n->val, maxval(n->next));
}

Can be transformed into:

unsigned maxval(struct Node *n) {
  struct Node *head = n;
  unsigned max = 0; // Identity of unsigned std::max
  while (true) {
    if (!head) return max;
    max = std::max(max, head->val);
    head = head->next;
  }
  return max;
}

This example results in about 5x speedup in local runs.

We conservatively only consider min/max and saturating add intrinsics as
associative for this patch to limit testing scope. There are probably
other intrinsics that could be considered associative. There are a few
consumers of isAssociative() that could be impacted. Testing has only
required to Reassociate pass be updated.

Diff Detail

Event Timeline

caojoshua created this revision.May 14 2023, 10:33 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 14 2023, 10:33 PM
caojoshua edited the summary of this revision. (Show Details)

Update commit msg

caojoshua edited the summary of this revision. (Show Details)

include basic benchmark note in commit msg

caojoshua edited the summary of this revision. (Show Details)

Note on updates in other passes

caojoshua published this revision for review.May 14 2023, 11:13 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 14 2023, 11:13 PM