path: root/lib/CodeGen/PBQP.cpp

//===---------------- PBQP.cpp --------- PBQP Solver ------------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Developed by:                   Bernhard Scholz
//                             The University of Sydney
//                         http://www.it.usyd.edu.au/~scholz
//===----------------------------------------------------------------------===//

#include "PBQP.h"
#include "llvm/Config/alloca.h"
#include <limits>
#include <cassert>
#include <cstring>

namespace llvm {

/**************************************************************************
 * Data Structures 
 **************************************************************************/

/* edge of PBQP graph */
typedef struct adjnode {
  struct adjnode *prev,      /* doubly chained list */ 
                 *succ, 
                 *reverse;   /* reverse edge */
  int adj;                   /* adj. node */
  PBQPMatrix *costs;         /* cost matrix of edge */

  bool tc_valid;              /* flag whether following fields are valid */
  int *tc_safe_regs;          /* safe registers */
  int tc_impact;              /* impact */ 
} adjnode;

/* bucket node */
typedef struct bucketnode {
  struct bucketnode *prev;   /* doubly chained list */
  struct bucketnode *succ;   
  int u;                     /* node */
} bucketnode;

/* data structure of partitioned boolean quadratic problem */
struct pbqp {
  int num_nodes;             /* number of nodes */
  int max_deg;               /* maximal degree of a node */
  bool solved;               /* flag that indicates whether PBQP has been solved yet */
  bool optimal;              /* flag that indicates whether PBQP is optimal */
  PBQPNum min;
  bool changed;              /* flag whether graph has changed in simplification */

                             /* node fields */
  PBQPVector **node_costs;   /* cost vectors of nodes */
  int *node_deg;             /* node degree of nodes */
  int *solution;             /* solution for node */
  adjnode **adj_list;        /* adj. list */
  bucketnode **bucket_ptr;   /* bucket pointer of a node */

                             /* node stack */
  int *stack;                /* stack of nodes */
  int stack_ptr;             /* stack pointer */

                             /* bucket fields */
  bucketnode **bucket_list;  /* bucket l