dragonegg/src/Aliasing.cpp

//=----------- Aliasing.cpp - Type-based alias analysis metadata ----------*-=//
//
// Copyright (C) 2012 to 2013  Duncan Sands.
//
// This file is part of DragonEgg.
//
// DragonEgg is free software; you can redistribute it and/or modify it under
// the terms of the GNU General Public License as published by the Free Software
// Foundation; either version 2, or (at your option) any later version.
//
// DragonEgg is distributed in the hope that it will be useful, but WITHOUT ANY
// WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
// A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License along with
// DragonEgg; see the file COPYING.  If not, write to the Free Software
// Foundation, 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA.
//
//===----------------------------------------------------------------------===//
// This file declares routines for generating TBAA metadata from what GCC knows
// about pointer aliasing.
//===----------------------------------------------------------------------===//

// Plugin headers
#include "dragonegg/Aliasing.h"
#include "llvm/ADT/SmallVector.h"

// LLVM headers
#include "llvm/ADT/Twine.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/Metadata.h"

// System headers
#include <gmp.h>
#include <map>

// GCC headers
#include "auto-host.h"
#ifndef ENABLE_BUILD_WITH_CXX
#include <cstring> // Otherwise included by system.h with C linkage.
extern "C" {
#endif
#include "config.h"
// Stop GCC declaring 'getopt' as it can clash with the system's declaration.
#undef HAVE_DECL_GETOPT
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"

#include "alias.h"
#ifndef ENABLE_BUILD_WITH_CXX
} // extern "C"
#endif

// Trees header.
#include "dragonegg/Trees.h"

using namespace llvm;

static LLVMContext &Context = getGlobalContext();

/// getTBAARoot - Return the root of the TBAA tree for this compilation unit.
static MDNode *getTBAARoot() {
  static MDNode *Root;
  if (!Root) {
    // Create the root node.  This must be unique to the compilation unit since
    // the names of the nodes we hang off it have no intrinsic meaning: nodes
    // from different compilation units must not be merged even if they have the
    // same name.
    MDBuilder MDHelper(Context);
    Root = MDHelper.createAnonymousTBAARoot();
  }
  return Root;
}

/// describeAliasSet - Return TBAA metadata describing what a load from or store
/// to the given tree may alias.
MDNode *describeAliasSet(tree t) {
  alias_set_type alias_set = get_alias_set(t);
  // Alias set 0 is the root of the alias graph and can alias anything.  A
  // negative value represents an unknown alias set, which as far as we know
  // may also alias anything.
  if (alias_set <= 0)
    return 0;

  // The difficulty here is that GCC's alias sets are the nodes of a directed
  // acyclic graph (DAG) rooted at 0, and in complicated cases it really is a
  // DAG and not a tree.  This is due to record types: the DAG has a node for
  // each record type with, for every field, an edge from the node to the node
  // for the field's type.  As a result the leaves of the DAG are usually scalar
  // types, with an incoming edge from every record type with a field with that
  // scalar type.  On the other hand, LLVM requires TBAA nodes to form a tree.
  // In short we need to come up with a tree and a graph map (i.e. a map that
  // takes nodes to nodes and edges to edges) from GCC's DAG to this tree.  (An
  // alternative is to complicate LLVM so that it too uses DAGs for TBAA).  An
  // additional difficulty is that we don't actually know the edges in the DAG:
  // GCC's alias analysis interface does not expose them.  All that we have is
  // alias_set_subset_of(s, t) which returns true iff there is a path from t to
  // s in the DAG.  Finally, we don't know the nodes of the DAG either!  We only
  // discover them progressively as we convert functions.
  // For the moment we take a very simple approach: we only use the leaf nodes
  // of GCC's DAG.  This means that we do a good job for scalars and a poor job
  // for record types, including complex types.
  static std::map<alias_set_type, MDNode *> NodeTags; // Node -> metadata map.
  static SmallVector<alias_set_type, 8> LeafNodes;    // Current set of leaves.

  std::map<alias_set_type, MDNode *>::iterator I = NodeTags.find(alias_set);
  if (I != NodeTags.end())
    return I->second;

  if (LeafNodes.empty())
    // Check for a GCC special case: a node can have an edge to the root node.
    // This is handled automatically (below) except when there are not yet any
    // known leaf nodes.
    if (alias_set_subset_of(0, alias_set)) {
      NodeTags[alias_set] = 0;
      return 0;
    }

  // If there is a path from this node to any leaf node then it is not a leaf
  // node and can be discarded.
  for (unsigned i = 0, e = (unsigned) LeafNodes.size(); i != e; ++i)
    if (alias_set_subset_of(LeafNodes[i], alias_set)) {
      NodeTags[alias_set] = 0;
      return 0;
    }
  assert(!alias_set_subset_of(0, alias_set) && "'May alias' not transitive?");

  // If there is a path from any leaf node to this one then no longer consider
  // that node to be a leaf.
  for (unsigned i = (unsigned) LeafNodes.size(); i;) {
    alias_set_type leaf_set = LeafNodes[--i];
    if (alias_set_subset_of(alias_set, leaf_set)) {
      LeafNodes.erase(LeafNodes.begin() + i);
      MDNode *&LeafTag = NodeTags[leaf_set];
      // It would be neat to strip the tbaa tag from any instructions using it
      // but it is simpler to just replace it with the root tag everywhere.
      LeafTag->replaceAllUsesWith(getTBAARoot());
      LeafTag = 0;
    }
  }

  // Create metadata describing the new node hanging off root.  The name doesn't
  // matter much but needs to be unique for the compilation unit.
  tree type =
      TYPE_CANONICAL(TYPE_MAIN_VARIANT(isa<TYPE>(t) ? t : TREE_TYPE(t)));
  std::string TreeName =
      ("alias set " + Twine(alias_set) + ": " + getDescriptiveName(type)).str();
  MDBuilder MDHelper(Context);

  MDNode *AliasTag = MDHelper.createTBAANode(TreeName, getTBAARoot());
  NodeTags[alias_set] = AliasTag;
  LeafNodes.push_back(alias_set);
  return AliasTag;
}