[CallGraph] Refine call graph for indirect calls with !callees metadata
authorMark Lacey <mark.lacey@apple.com>
Thu, 15 Aug 2019 17:47:53 +0000 (17:47 +0000)
committerMark Lacey <mark.lacey@apple.com>
Thu, 15 Aug 2019 17:47:53 +0000 (17:47 +0000)
commit626ed22fbe2cfc2043cef2d855743f029c67f73a
tree2b56bc2d51b4218252be85ca31e361dbb9609e17
parent213d8a9f1389eb565146e6323317ef436cb0da78
[CallGraph] Refine call graph for indirect calls with !callees metadata

For indirect call sites having a small set of possible callees,
!callees metadata can be used to indicate what those callees are.
This patch updates the call graph and lazy call graph analyses so
that they consider this metadata when encountering call sites. For
the call graph, it adds a new external call graph node to the graph
for each unique !callees metadata node. A call graph edge connects
an indirect call site with the external node associated with the
!callees metadata that is attached to it. And there is an edge from
this external node to each of the callees indicated by the metadata.
Similarly, for the lazy call graph, the patch adds Ref edges from a
caller to the possible callees indicated by the metadata.

The primary purpose of the patch is to facilitate iterating over the
functions in a module such that all of the callees indicated by a
given !callees metadata node will be visited prior to the functions
containing call sites annotated by that node. This property is
required by optimizations performing a bottom-up traversal of the
SCC DAG. For example, the inliner can be made to inline through an
indirect call. If the call site is annotated with !callees metadata,
this patch ensures that the inliner will have visited all of the
callees prior to the caller, allowing it to reliably compute the
cost of inlining one or more of the potential callees.

Original patch by @mssimpso. I've made some small changes to get it
to apply, build, and pass tests on the top of tree, as well as
some minor tweaks to formatting and functionality.

Subscribers: mehdi_amini, hiraditya, llvm-commits, mssimpso

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D39339

llvm-svn: 369025
llvm/include/llvm/Analysis/CallGraph.h
llvm/include/llvm/IR/CallSite.h
llvm/lib/Analysis/CGSCCPassManager.cpp
llvm/lib/Analysis/CallGraph.cpp
llvm/lib/Analysis/LazyCallGraph.cpp
llvm/test/Analysis/CallGraph/callees-metadata.ll [new file with mode: 0644]
llvm/test/Analysis/CallGraph/non-leaf-intrinsics.ll
llvm/test/Analysis/LazyCallGraph/callees-metadata.ll [new file with mode: 0644]