hphp/compiler/analysis/bit_set_vec.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2014 Facebook, Inc. (http://www.facebook.com)     |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #include <stdlib.h>
  18 #include "hphp/compiler/analysis/bit_set_vec.h"
  19 #include "hphp/compiler/analysis/data_flow.h"
  20
  21 using namespace HPHP;
  22
  23 BITOP_DEFINE1(bit_copy);
  24 BITOP_DEFINE1(bit_complement);
  25 BITOP_DEFINE2(bit_and)
  26 BITOP_DEFINE2(bit_or)
  27 BITOP_DEFINE2(bit_xor)
  28 BITOP_DEFINE3(bit_and_and)
  29 BITOP_DEFINE3(bit_or_or)
  30 BITOP_DEFINE3(bit_and_or)
  31 BITOP_DEFINE3(bit_or_and)
  32 BITOP_DEFINE3(bit_or_andc)
  33 BITOP_DEFINE3(bit_andc_or)
  34
  35 void BitSetVec::alloc(int blocks, size_t width, int rows, int *rowIds) {
  36   reset();
  37
  38   m_width = width;
  39   m_maxId = 0;
  40
  41   bool noTranslate = rows < 0;
  42   if (noTranslate) {
  43     m_maxId = rows = -rows;
  44   } else {
  45     for (int i = 0; i < rows; i++) {
  46       int rid = rowIds[i];
  47       if (rid >= m_maxId) m_maxId = rid + 1;
  48     }
  49   }
  50
  51   m_rowSize = (width + elemSize - 1) / elemSize * sizeof(BitOps::Bits);
  52   m_idOffsets = (size_t*)calloc(m_maxId, sizeof(size_t));
  53   for (int i = 0; i < rows; i++) {
  54     int rid = noTranslate ? i : rowIds[i];
  55     m_idOffsets[rid] = i * m_rowSize + 1;
  56   }
  57   m_blockSize = m_rowSize * rows;
  58   m_bits = (BitOps::Bits*)calloc(m_blockSize, blocks);
  59   if (!noTranslate) {
  60     size_t offset = 0;
  61     for (int b = 0; b < blocks; b++) {
  62       for (int i = 0; i < rows; i++) {
  63         if (DataFlow::GetInit(rowIds[i])) {
  64           memset(add(m_bits, offset), 255, m_rowSize);
  65         }
  66         offset += m_rowSize;
  67       }
  68     }
  69   }
  70 }
  71
  72 void BitSetVec::reset() {
  73   free(m_idOffsets);
  74   free(m_bits);
  75 }
  76
  77 BitSetBlock BitSetVec::getBlock(int block) {
  78   return BitSetBlock(add(m_bits, block * m_blockSize), *this);
  79 }
  80
  81 BitOps::Bits *BitSetVec::getTempBits(int id) const {
  82   size_t offset = id * m_rowSize;
  83   always_assert(offset < m_blockSize);
  84
  85   return add(m_bits, offset);
  86 }
  87
  88 BitOps::Bits *BitSetBlock::getRow(int row) const {
  89   size_t offset = m_owner->rowOffset(row);
  90   always_assert(offset != (size_t)-1);
  91   return BitSetVec::add(m_bits, offset);
  92 }
  93
  94 void BitSetBlock::setBit(int row, int id, bool v) {
  95   BitOps::Bits *bits = getRow(row);
  96   always_assert((unsigned)id < m_owner->width());
  97   BitOps::set_bit(id, bits, v);
  98 }
  99
 100 bool BitSetBlock::getBit(int row, int id) const {
 101   BitOps::Bits *bits = getRow(row);
 102   always_assert((unsigned)id < m_owner->width());
 103   return BitOps::get_bit(id, bits);
 104 }
 105
 106 bool BitOps::bit_equal(size_t width, Bits *in1, Bits *in2) {
 107   while (width >= BitSetVec::elemSize) {
 108     if (*in1++ != *in2++) return false;
 109     width -= BitSetVec::elemSize;
 110   }
 111   if (!width) return true;
 112   Bits mask = ~((Bits)-1 << width);
 113   return (*in1 & mask) == (*in2 & mask);
 114 }
 115
 116 void BitOps::set(size_t width, Bits *out, Bits value) {
 117   width += elemSize - 1;
 118   while (width >= elemSize) {
 119     *out++ = value;
 120     width -= elemSize;
 121   }
 122 }
 123
 124 bool BitOps::get_bit(size_t bit, Bits *bits) {
 125   size_t offset = bit / BitSetVec::elemSize;
 126   int b = bit % BitSetVec::elemSize;
 127   return (bits[offset] >> b) & 1;
 128 }
 129
 130 void BitOps::set_bit(size_t bit, Bits *bits, bool value) {
 131   size_t offset = bit / BitSetVec::elemSize;
 132   int b = bit % BitSetVec::elemSize;
 133   Bits m = ~((Bits)1 << b);
 134   Bits v = (Bits)value << b;
 135   bits[offset] = (bits[offset] & m) | v;
 136 }
 137