/home/daniel/Projects/java/jdk/src/hotspot/share/adlc/dfa.cpp

Bug Summary

File:	jdk/src/hotspot/share/adlc/dfa.cpp
Warning:	line 553, column 12 Potential leak of memory pointed to by 'new_pred'
Annotated Source Code

Press '?' to see keyboard shortcuts
Show analyzer invocation
clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name dfa.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model static -mthread-model posix -mframe-pointer=all -fmath-errno -fno-rounding-math -masm-verbose -mconstructor-aliases -munwind-tables -target-cpu x86-64 -dwarf-column-info -fno-split-dwarf-inlining -debugger-tuning=gdb -resource-dir /usr/lib/llvm-10/lib/clang/10.0.0 -D LINUX -D ASSERT -D AMD64 -I /home/daniel/Projects/java/jdk/src/hotspot/share -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/x86_64-linux-gnu/c++/7.5.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/x86_64-linux-gnu/c++/7.5.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-10/lib/clang/10.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -Wno-unused-parameter -Wno-unused -fdeprecated-macro -fdebug-compilation-dir /home/daniel/Projects/java/jdk/make/hotspot -ferror-limit 19 -fmessage-length 0 -fgnuc-version=4.2.1 -fobjc-runtime=gcc -fdiagnostics-show-option -analyzer-output=html -faddrsig -o /home/daniel/Projects/java/scan/2021-12-21-193737-8510-1 -x c++ /home/daniel/Projects/java/jdk/src/hotspot/share/adlc/dfa.cpp
1/*
* Copyright (c) 1997, 2018, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation.
*
* This code 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
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*
*/

25// DFA.CPP - Method definitions for outputting the matcher DFA from ADLC
26#include "adlc.hpp"

28//---------------------------Switches for debugging output---------------------
29static bool debug_output   = false;
30static bool debug_output1  = false;    // top level chain rules

32//---------------------------Production State----------------------------------
33static const char *knownInvalid = "knownInvalid";    // The result does NOT have a rule defined
34static const char *knownValid   = "knownValid";      // The result must be produced by a rule
35static const char *unknownValid = "unknownValid";    // Unknown (probably due to a child or predicate constraint)

37static const char *noConstraint  = "noConstraint";   // No constraints seen so far
38static const char *hasConstraint = "hasConstraint";  // Within the first constraint


41//------------------------------Production------------------------------------
42// Track the status of productions for a particular result
43class Production {
44public:
const char *_result;
const char *_constraint;
const char *_valid;
Expr       *_cost_lb;            // Cost lower bound for this production
Expr       *_cost_ub;            // Cost upper bound for this production

51public:
Production(const char *result, const char *constraint, const char *valid);
~Production() {};

void        initialize();        // reset to be an empty container

const char   *valid()  const { return _valid; }
Expr       *cost_lb()  const { return (Expr *)_cost_lb;  }
Expr       *cost_ub()  const { return (Expr *)_cost_ub;  }

void print();
62};


65//------------------------------ProductionState--------------------------------
66// Track the status of all production rule results
67// Reset for each root opcode (e.g., Op_RegI, Op_AddI, ...)
68class ProductionState {
69private:
Dict _production;    // map result of production, char*, to information or NULL
const char *_constraint;

73public:
// cmpstr does string comparisions.  hashstr computes a key.
ProductionState(Arena *arena) : _production(cmpstr, hashstr, arena) { initialize(); };
~ProductionState() { };

void        initialize();                // reset local and dictionary state

const char *constraint();
void    set_constraint(const char *constraint); // currently working inside of constraints

const char *valid(const char *result);   // unknownValid, or status for this production
void    set_valid(const char *result);   // if not constrained, set status to knownValid

Expr           *cost_lb(const char *result);
Expr           *cost_ub(const char *result);
void    set_cost_bounds(const char *result, const Expr *cost, bool has_state_check, bool has_cost_check);

// Return the Production associated with the result,
// or create a new Production and insert it into the dictionary.
Production *getProduction(const char *result);

void print();

96private:
  // Disable public use of constructor, copy-ctor,  ...
ProductionState( )                         : _production(cmpstr, hashstr, Form::arena) {  assert( false, "NotImplemented"){ if (!(false)) { fprintf(stderr, "assert fails %s %d: %s\n",
 "/home/daniel/Projects/java/jdk/src/hotspot/share/adlc/dfa.cpp"
, 98, "NotImplemented"); abort(); }};  };
ProductionState( const ProductionState & ) : _production(cmpstr, hashstr, Form::arena) {  assert( false, "NotImplemented"){ if (!(false)) { fprintf(stderr, "assert fails %s %d: %s\n",
 "/home/daniel/Projects/java/jdk/src/hotspot/share/adlc/dfa.cpp"
, 99, "NotImplemented"); abort(); }};  }; // Deep-copy
100};


103//---------------------------Helper Functions----------------------------------
104// cost_check template:
105// 1)      if (STATE__NOT_YET_VALID(EBXREGI) || _cost[EBXREGI] > c) {
106// 2)        DFA_PRODUCTION(EBXREGI, cmovI_memu_rule, c)
107// 3)      }
108//
109static void cost_check(FILE *fp, const char *spaces,
                     const char *arrayIdx, const Expr *cost, const char *rule, ProductionState &status) {
bool state_check               = false;  // true if this production needs to check validity
bool cost_check                = false;  // true if this production needs to check cost
bool cost_is_above_upper_bound = false;  // true if this production is unnecessary due to high cost
bool cost_is_below_lower_bound = false;  // true if this production replaces a higher cost production

// Get information about this production
const Expr *previous_ub = status.cost_ub(arrayIdx);
if( !previous_ub->is_unknown() ) {
  if( previous_ub->less_than_or_equal(cost) ) {
    cost_is_above_upper_bound = true;
    if( debug_output ) { fprintf(fp, "// Previous rule with lower cost than: %s === %s_rule costs %s\n", arrayIdx, rule, cost->as_string()); }
  }
}

const Expr *previous_lb = status.cost_lb(arrayIdx);
if( !previous_lb->is_unknown() ) {
  if( cost->less_than_or_equal(previous_lb) ) {
    cost_is_below_lower_bound = true;
    if( debug_output ) { fprintf(fp, "// Previous rule with higher cost\n"); }
  }
}

// line 1)
// Check for validity and compare to other match costs
const char *validity_check = status.valid(arrayIdx);
if( validity_check == unknownValid ) {
  fprintf(fp, "%sif (STATE__NOT_YET_VALID(%s) || _cost[%s] > %s) {\n",  spaces, arrayIdx, arrayIdx, cost->as_string());
  state_check = true;
  cost_check  = true;
}
else if( validity_check == knownInvalid ) {
  if( debug_output ) { fprintf(fp, "%s// %s KNOWN_INVALID \n",  spaces, arrayIdx); }
}
else if( validity_check == knownValid ) {
  if( cost_is_above_upper_bound ) {
    // production cost is known to be too high.
    return;
  } else if( cost_is_below_lower_bound ) {
    // production will unconditionally overwrite a previous production that had higher cost
  } else {
    fprintf(fp, "%sif ( /* %s KNOWN_VALID || */ _cost[%s] > %s) {\n",  spaces, arrayIdx, arrayIdx, cost->as_string());
    cost_check  = true;
  }
}

// line 2)
fprintf(fp, "%s  DFA_PRODUCTION(%s, %s_rule, %s)", spaces, arrayIdx, rule, cost->as_string() );
if (validity_check == knownValid) {
  if (cost_is_below_lower_bound) {
    fprintf(fp, "\t  // overwrites higher cost rule");
  }
}
fprintf(fp, "\n");

// line 3)
if( cost_check || state_check ) {
  fprintf(fp, "%s}\n", spaces);
}

status.set_cost_bounds(arrayIdx, cost, state_check, cost_check);

// Update ProductionState
if( validity_check != knownValid ) {
  // set State vector if not previously known
  status.set_valid(arrayIdx);
}
177}


180//---------------------------child_test----------------------------------------
181// Example:
182//   STATE__VALID_CHILD(_kids[0], FOO) &&  STATE__VALID_CHILD(_kids[1], BAR)
183// Macro equivalent to: _kids[0]->valid(FOO) && _kids[1]->valid(BAR)
184//
185static void child_test(FILE *fp, MatchList &mList) {
if (mList._lchild) { // If left child, check it
  const char* lchild_to_upper = ArchDesc::getMachOperEnum(mList._lchild);
  fprintf(fp, "STATE__VALID_CHILD(_kids[0], %s)", lchild_to_upper);
  delete[] lchild_to_upper;
}
if (mList._lchild && mList._rchild) { // If both, add the "&&"
  fprintf(fp, " && ");
}
if (mList._rchild) { // If right child, check it
  const char* rchild_to_upper = ArchDesc::getMachOperEnum(mList._rchild);
  fprintf(fp, "STATE__VALID_CHILD(_kids[1], %s)", rchild_to_upper);
  delete[] rchild_to_upper;
}
199}

201//---------------------------calc_cost-----------------------------------------
202// Example:
203//           unsigned int c = _kids[0]->_cost[FOO] + _kids[1]->_cost[BAR] + 5;
204//
205Expr *ArchDesc::calc_cost(FILE *fp, const char *spaces, MatchList &mList, ProductionState &status) {
fprintf(fp, "%sunsigned int c = ", spaces);
Expr *c = new Expr("0");
if (mList._lchild) { // If left child, add it in
  const char* lchild_to_upper = ArchDesc::getMachOperEnum(mList._lchild);
  sprintf(Expr::buffer(), "_kids[0]->_cost[%s]", lchild_to_upper);
  c->add(Expr::buffer());
  delete[] lchild_to_upper;
213}
if (mList._rchild) { // If right child, add it in
  const char* rchild_to_upper = ArchDesc::getMachOperEnum(mList._rchild);
  sprintf(Expr::buffer(), "_kids[1]->_cost[%s]", rchild_to_upper);
  c->add(Expr::buffer());
  delete[] rchild_to_upper;
}
// Add in cost of this rule
const char *mList_cost = mList.get_cost();
c->add(mList_cost, *this);

fprintf(fp, "%s;\n", c->as_string());
c->set_external_name("c");
return c;
227}


230//---------------------------gen_match-----------------------------------------
231void ArchDesc::gen_match(FILE *fp, MatchList &mList, ProductionState &status, Dict &operands_chained_from) {
const char *spaces4 = "    ";
const char *spaces6 = "      ";

fprintf(fp, "%s", spaces4);
// Only generate child tests if this is not a leaf node
bool has_child_constraints = mList._lchild || mList._rchild;
const char *predicate_test = mList.get_pred();
if (has_child_constraints || predicate_test) {
  // Open the child-and-predicate-test braces
  fprintf(fp, "if( ");
  status.set_constraint(hasConstraint);
  child_test(fp, mList);
  // Only generate predicate test if one exists for this match
  if (predicate_test) {
    if (has_child_constraints) {
      fprintf(fp," &&\n");
    }
    fprintf(fp, "%s  %s", spaces6, predicate_test);
  }
  // End of outer tests
  fprintf(fp," ) ");
} else {
  // No child or predicate test needed
  status.set_constraint(noConstraint);
}

// End of outer tests
fprintf(fp,"{\n");

// Calculate cost of this match
const Expr *cost = calc_cost(fp, spaces6, mList, status);
// Check against other match costs, and update cost & rule vectors
cost_check(fp, spaces6, ArchDesc::getMachOperEnum(mList._resultStr), cost, mList._opcode, status);

// If this is a member of an operand class, update the class cost & rule
expand_opclass( fp, spaces6, cost, mList._resultStr, status);

// Check if this rule should be used to generate the chains as well.
const char *rule = /* set rule to "Invalid" for internal operands */
  strcmp(mList._opcode, mList._resultStr) ? mList._opcode : "Invalid";

// If this rule produces an operand which has associated chain rules,
// update the operands with the chain rule + this rule cost & this rule.
chain_rule(fp, spaces6, mList._resultStr, cost, rule, operands_chained_from, status);

// Close the child-and-predicate-test braces
fprintf(fp, "    }\n");

280}


283//---------------------------expand_opclass------------------------------------
284// Chain from one result_type to all other members of its operand class
285void ArchDesc::expand_opclass(FILE *fp, const char *indent, const Expr *cost,
                            const char *result_type, ProductionState &status) {
const Form *form = _globalNames[result_type];
OperandForm *op = form ? form->is_operand() : NULL__null;
if( op && op->_classes.count() > 0 ) {
  if( debug_output ) { fprintf(fp, "// expand operand classes for operand: %s \n", (char *)op->_ident  ); } // %%%%% Explanation
  // Iterate through all operand classes which include this operand
  op->_classes.reset();
  const char *oclass;
  // Expr *cCost = new Expr(cost);
  while( (oclass = op->_classes.iter()) != NULL__null )
    // Check against other match costs, and update cost & rule vectors
    cost_check(fp, indent, ArchDesc::getMachOperEnum(oclass), cost, result_type, status);
}
299}

301//---------------------------chain_rule----------------------------------------
302// Starting at 'operand', check if we know how to automatically generate other results
303void ArchDesc::chain_rule(FILE *fp, const char *indent, const char *operand,
   const Expr *icost, const char *irule, Dict &operands_chained_from,  ProductionState &status) {

// Check if we have already generated chains from this starting point
if( operands_chained_from[operand] != NULL__null ) {
  return;
} else {
  operands_chained_from.Insert( operand, operand);
}
if( debug_output ) { fprintf(fp, "// chain rules starting from: %s  and  %s \n", (char *)operand, (char *)irule); } // %%%%% Explanation

ChainList *lst = (ChainList *)_chainRules[operand];
if (lst) {
  // printf("\nChain from <%s> at cost #%s\n",operand, icost ? icost : "_");
  const char *result, *cost, *rule;
  for(lst->reset(); (lst->iter(result,cost,rule)) == true; ) {
    // Do not generate operands that are already available
    if( operands_chained_from[result] != NULL__null ) {
      continue;
    } else {
      // Compute the cost for previous match + chain_rule_cost
      // total_cost = icost + cost;
      Expr *total_cost = icost->clone();  // icost + cost
      total_cost->add(cost, *this);

      // Check for transitive chain rules
      Form *form = (Form *)_globalNames[rule];
      if ( ! form->is_instruction()) {
        // printf("   result=%s cost=%s rule=%s\n", result, total_cost, rule);
        // Check against other match costs, and update cost & rule vectors
        const char *reduce_rule = strcmp(irule,"Invalid") ? irule : rule;
        cost_check(fp, indent, ArchDesc::getMachOperEnum(result), total_cost, reduce_rule, status);
        chain_rule(fp, indent, result, total_cost, irule, operands_chained_from, status);
      } else {
        // printf("   result=%s cost=%s rule=%s\n", result, total_cost, rule);
        // Check against other match costs, and update cost & rule vectors
        cost_check(fp, indent, ArchDesc::getMachOperEnum(result), total_cost, rule, status);
        chain_rule(fp, indent, result, total_cost, rule, operands_chained_from, status);
      }

      // If this is a member of an operand class, update class cost & rule
      expand_opclass( fp, indent, total_cost, result, status );
    }
  }
}
348}

350//---------------------------prune_matchlist-----------------------------------
351// Check for duplicate entries in a matchlist, and prune out the higher cost
352// entry.
353void ArchDesc::prune_matchlist(Dict &minimize, MatchList &mlist) {

355}

357//---------------------------buildDFA------------------------------------------
358// DFA is a large switch with case statements for each ideal opcode encountered
359// in any match rule in the ad file.  Each case has a series of if's to handle
360// the match or fail decisions.  The matches test the cost function of that
361// rule, and prune any cases which are higher cost for the same reduction.
362// In order to generate the DFA we walk the table of ideal opcode/MatchList
363// pairs generated by the ADLC front end to build the contents of the case
364// statements (a series of if statements).
365void ArchDesc::buildDFA(FILE* fp) {
int i;
// Remember operands that are the starting points for chain rules.
// Prevent cycles by checking if we have already generated chain.
Dict operands_chained_from(cmpstr, hashstr, Form::arena);

// Hash inputs to match rules so that final DFA contains only one entry for
// each match pattern which is the low cost entry.
Dict minimize(cmpstr, hashstr, Form::arena);

// Track status of dfa for each resulting production
// reset for each ideal root.
ProductionState status(Form::arena);

// Output the start of the DFA method into the output file

fprintf(fp, "\n");
fprintf(fp, "//------------------------- Source -----------------------------------------\n");
// Do not put random source code into the DFA.
// If there are constants which need sharing, put them in "source_hpp" forms.
// _source.output(fp);
fprintf(fp, "\n");
fprintf(fp, "//------------------------- Attributes -------------------------------------\n");
_attributes.output(fp);
fprintf(fp, "\n");
fprintf(fp, "//------------------------- Macros -----------------------------------------\n");
fprintf(fp, "#define DFA_PRODUCTION(result, rule, cost)\\\n");
fprintf(fp, "  assert(rule < (1 << 15), \"too many rules\"); _cost[ (result) ] = cost; _rule[ (result) ] = (rule << 1) | 0x1;\n");
fprintf(fp, "\n");

fprintf(fp, "//------------------------- DFA --------------------------------------------\n");

fprintf(fp,
398"// DFA is a large switch with case statements for each ideal opcode encountered\n"
399"// in any match rule in the ad file.  Each case has a series of if's to handle\n"
400"// the match or fail decisions.  The matches test the cost function of that\n"
401"// rule, and prune any cases which are higher cost for the same reduction.\n"
402"// In order to generate the DFA we walk the table of ideal opcode/MatchList\n"
403"// pairs generated by the ADLC front end to build the contents of the case\n"
404"// statements (a series of if statements).\n"
405);
fprintf(fp, "\n");
fprintf(fp, "\n");
if (_dfa_small) {
1
Assuming field '_dfa_small' is not equal to 0→
2
←
Taking true branch→
  // Now build the individual routines just like the switch entries in large version
  // Iterate over the table of MatchLists, start at first valid opcode of 1
  for (i = 1; i < _last_opcode; i++) {
3
←
Loop condition is true.  Entering loop body→
    if (_mlistab[i] == NULL__null) continue;
4
←
Assuming the condition is false→
5
←
Taking false branch→
    // Generate the routine header statement for this opcode
    fprintf(fp, "void  State::_sub_Op_%s(const Node *n){\n", NodeClassNames[i]);
    // Generate body. Shared for both inline and out-of-line version
    gen_dfa_state_body(fp, minimize, status, operands_chained_from, i);
6
←
Calling 'ArchDesc::gen_dfa_state_body'→
    // End of routine
    fprintf(fp, "}\n");
  }
}
fprintf(fp, "bool State::DFA");
fprintf(fp, "(int opcode, const Node *n) {\n");
fprintf(fp, "  switch(opcode) {\n");

// Iterate over the table of MatchLists, start at first valid opcode of 1
for (i = 1; i < _last_opcode; i++) {
  if (_mlistab[i] == NULL__null) continue;
  // Generate the case statement for this opcode
  if (_dfa_small) {
    fprintf(fp, "  case Op_%s: { _sub_Op_%s(n);\n", NodeClassNames[i], NodeClassNames[i]);
  } else {
    fprintf(fp, "  case Op_%s: {\n", NodeClassNames[i]);
    // Walk the list, compacting it
    gen_dfa_state_body(fp, minimize, status, operands_chained_from, i);
  }
  // Print the "break"
  fprintf(fp, "    break;\n");
  fprintf(fp, "  }\n");
}

// Generate the default case for switch(opcode)
fprintf(fp, "  \n");
fprintf(fp, "  default:\n");
fprintf(fp, "    tty->print(\"Default case invoked for: \\n\");\n");
fprintf(fp, "    tty->print(\"   opcode  = %cd, \\\"%cs\\\"\\n\", opcode, NodeClassNames[opcode]);\n", '%', '%');
fprintf(fp, "    return false;\n");
fprintf(fp, "  }\n");

// Return status, indicating a successful match.
fprintf(fp, "  return true;\n");
// Generate the closing brace for method Matcher::DFA
fprintf(fp, "}\n");
Expr::check_buffers();
454}


457class dfa_shared_preds {
enum { count = 3 IA32_ONLY( + 1 ) };

static bool        _found[count];
static const char* _type [count];
static const char* _var  [count];
static const char* _pred [count];

static void check_index(int index) { assert( 0 <= index && index < count, "Invalid index"){ if (!(0 <= index && index < count)) { fprintf
(stderr, "assert fails %s %d: %s\n", "/home/daniel/Projects/java/jdk/src/hotspot/share/adlc/dfa.cpp"
, 465, "Invalid index"); abort(); }}; }

// Confirm that this is a separate sub-expression.
// Only need to catch common cases like " ... && shared ..."
// and avoid hazardous ones like "...->shared"
static bool valid_loc(char *pred, char *shared) {
  // start of predicate is valid
  if( shared == pred ) return true;

  // Check previous character and recurse if needed
  char *prev = shared - 1;
  char c  = *prev;
  switch( c ) {
  case ' ':
  case '\n':
    return dfa_shared_preds::valid_loc(pred, prev);
  case '!':
  case '(':
  case '<':
  case '=':
    return true;
  case '"':  // such as: #line 10 "myfile.ad"\n mypredicate
    return true;
  case '|':
    if (prev != pred && *(prev-1) == '|') return true;
    break;
  case '&':
    if (prev != pred && *(prev-1) == '&') return true;
    break;
  default:
    return false;
  }

  return false;
}

501public:

static bool        found(int index){ check_index(index); return _found[index]; }
static void    set_found(int index, bool val) { check_index(index); _found[index] = val; }
static void  reset_found() {
  for( int i = 0; i < count; ++i ) { _found[i] = false; }
};

static const char* type(int index) { check_index(index); return _type[index]; }
static const char* var (int index) { check_index(index); return _var [index];  }
static const char* pred(int index) { check_index(index); return _pred[index]; }

// Check each predicate in the MatchList for common sub-expressions
static void cse_matchlist(MatchList *matchList) {
  for( MatchList *mList = matchList; mList9.1
'mList' is not equal to NULL
 != NULL__null; mList = mList->get_next() ) {
10
←
Loop condition is true.  Entering loop body→
    Predicate* predicate = mList->get_pred_obj();
    char*      pred      = mList->get_pred();
    if( pred != NULL__null ) {
11
←
Assuming 'pred' is not equal to NULL→
12
←
Taking true branch→
      for(int index = 0; index < count; ++index ) {
13
←
Loop condition is true.  Entering loop body→
        const char *shared_pred      = dfa_shared_preds::pred(index);
        const char *shared_pred_var  = dfa_shared_preds::var(index);
        bool result = dfa_shared_preds::cse_predicate(predicate, shared_pred, shared_pred_var);
14
←
Calling 'dfa_shared_preds::cse_predicate'→
        if( result ) dfa_shared_preds::set_found(index, true);
      }
    }
  }
}

// If the Predicate contains a common sub-expression, replace the Predicate's
// string with one that uses the variable name.
static bool cse_predicate(Predicate* predicate, const char *shared_pred, const char *shared_pred_var) {
  bool result = false;
  char *pred = predicate->_pred;
  if( pred14.1
'pred' is not equal to NULL
 != NULL__null ) {
15
←
Taking true branch→
    char *new_pred = pred;
    for( char *shared_pred_loc = strstr(new_pred, shared_pred);
17
←
Loop condition is true.  Entering loop body→
    shared_pred_loc != NULL__null && dfa_shared_preds::valid_loc(new_pred,shared_pred_loc);
16
←
Assuming 'shared_pred_loc' is not equal to NULL→
20
←
Assuming 'shared_pred_loc' is equal to NULL→
    shared_pred_loc = strstr(new_pred, shared_pred) ) {
      // Do not modify the original predicate string, it is shared
      if( new_pred17.1
'new_pred' is equal to 'pred'
 == pred ) {
18
←
Taking true branch→
        new_pred = strdup(pred);
19
←
Memory is allocated→
        shared_pred_loc = strstr(new_pred, shared_pred);
      }
      // Replace shared_pred with variable name
      strncpy(shared_pred_loc, shared_pred_var, strlen(shared_pred_var));
    }
    // Install new predicate
    if( new_pred != pred ) {
21
←
Assuming 'new_pred' is equal to 'pred'→
22
←
Taking false branch→
      predicate->_pred = new_pred;
      result = true;
    }
  }
  return result;
23
←
Potential leak of memory pointed to by 'new_pred'
}

// Output the hoisted common sub-expression if we found it in predicates
static void generate_cse(FILE *fp) {
  for(int j = 0; j < count; ++j ) {
    if( dfa_shared_preds::found(j) ) {
      const char *shared_pred_type = dfa_shared_preds::type(j);
      const char *shared_pred_var  = dfa_shared_preds::var(j);
      const char *shared_pred      = dfa_shared_preds::pred(j);
      fprintf(fp, "    %s %s = %s;\n", shared_pred_type, shared_pred_var, shared_pred);
    }
  }
}
567};
568// shared predicates, _var and _pred entry should be the same length
569bool         dfa_shared_preds::_found[dfa_shared_preds::count] = { false,          false,           false               IA32_ONLY(COMMA false)  };
570const char*  dfa_shared_preds::_type [dfa_shared_preds::count] = { "int",          "jlong",         "intptr_t"          IA32_ONLY(COMMA "bool") };
571const char*  dfa_shared_preds::_var  [dfa_shared_preds::count] = { "_n_get_int__", "_n_get_long__", "_n_get_intptr_t__" IA32_ONLY(COMMA "Compile__current____select_24_bit_instr__") };
572const char*  dfa_shared_preds::_pred [dfa_shared_preds::count] = { "n->get_int()", "n->get_long()", "n->get_intptr_t()" IA32_ONLY(COMMA "Compile::current()->select_24_bit_instr()") };

574void ArchDesc::gen_dfa_state_body(FILE* fp, Dict &minimize, ProductionState &status, Dict &operands_chained_from, int i) {
// Start the body of each Op_XXX sub-dfa with a clean state.
status.initialize();

// Walk the list, compacting it
MatchList* mList = _mlistab[i];
do {
8
←
Loop condition is false.  Exiting loop→
  // Hash each entry using inputs as key and pointer as data.
  // If there is already an entry, keep the one with lower cost, and
  // remove the other one from the list.
  prune_matchlist(minimize, *mList);
  // Iterate
  mList = mList->get_next();
} while(mList != NULL__null);
7
←
Assuming 'mList' is equal to NULL→

// Hoist previously specified common sub-expressions out of predicates
dfa_shared_preds::reset_found();
dfa_shared_preds::cse_matchlist(_mlistab[i]);
9
←
Calling 'dfa_shared_preds::cse_matchlist'→
dfa_shared_preds::generate_cse(fp);

mList = _mlistab[i];

// Walk the list again, generating code
do {
  // Each match can generate its own chains
  operands_chained_from.Clear();
  gen_match(fp, *mList, status, operands_chained_from);
  mList = mList->get_next();
} while(mList != NULL__null);
// Fill in any chain rules which add instructions
// These can generate their own chains as well.
operands_chained_from.Clear();  //
if( debug_output1 ) { fprintf(fp, "// top level chain rules for: %s \n", (char *)NodeClassNames[i]); } // %%%%% Explanation
const Expr *zeroCost = new Expr("0");
chain_rule(fp, "   ", (char *)NodeClassNames[i], zeroCost, "Invalid",
           operands_chained_from, status);
610}



614//------------------------------Expr------------------------------------------
615Expr *Expr::_unknown_expr = NULL__null;
616char  Expr::string_buffer[STRING_BUFFER_LENGTH2048];
617char  Expr::external_buffer[STRING_BUFFER_LENGTH2048];
618bool  Expr::_init_buffers = Expr::init_buffers();

620Expr::Expr() {
_external_name = NULL__null;
_expr          = "Invalid_Expr";
_min_value     = Expr::Max;
_max_value     = Expr::Zero;
625}
626Expr::Expr(const char *cost) {
_external_name = NULL__null;

int intval = 0;
if( cost == NULL__null ) {
  _expr = "0";
  _min_value = Expr::Zero;
  _max_value = Expr::Zero;
}
else if( ADLParser::is_int_token(cost, intval) ) {
  _expr = cost;
  _min_value = intval;
  _max_value = intval;
}
else {
  assert( strcmp(cost,"0") != 0, "Recognize string zero as an int"){ if (!(strcmp(cost,"0") != 0)) { fprintf(stderr, "assert fails %s %d: %s\n"
, "/home/daniel/Projects/java/jdk/src/hotspot/share/adlc/dfa.cpp"
, 641, "Recognize string zero as an int"); abort(); }};
  _expr = cost;
  _min_value = Expr::Zero;
  _max_value = Expr::Max;
}
646}

648Expr::Expr(const char *name, const char *expression, int min_value, int max_value) {
_external_name = name;
_expr          = expression ? expression : name;
_min_value     = min_value;
_max_value     = max_value;
assert(_min_value >= 0 && _min_value <= Expr::Max, "value out of range"){ if (!(_min_value >= 0 && _min_value <= Expr::
Max)) { fprintf(stderr, "assert fails %s %d: %s\n", "/home/daniel/Projects/java/jdk/src/hotspot/share/adlc/dfa.cpp"
, 653, "value out of range"); abort(); }};
assert(_max_value >= 0 && _max_value <= Expr::Max, "value out of range"){ if (!(_max_value >= 0 && _max_value <= Expr::
Max)) { fprintf(stderr, "assert fails %s %d: %s\n", "/home/daniel/Projects/java/jdk/src/hotspot/share/adlc/dfa.cpp"
, 654, "value out of range"); abort(); }};
655}

657Expr *Expr::clone() const {
Expr *cost = new Expr();
cost->_external_name = _external_name;
cost->_expr          = _expr;
cost->_min_value     = _min_value;
cost->_max_value     = _max_value;

return cost;
665}

667void Expr::add(const Expr *c) {
// Do not update fields until all computation is complete
const char *external  = compute_external(this, c);
const char *expr      = compute_expr(this, c);
int         min_value = compute_min (this, c);
int         max_value = compute_max (this, c);

_external_name = external;
_expr      = expr;
_min_value = min_value;
_max_value = max_value;
678}

680void Expr::add(const char *c) {
Expr *cost = new Expr(c);
add(cost);
683}

685void Expr::add(const char *c, ArchDesc &AD) {
const Expr *e = AD.globalDefs()[c];
if( e != NULL__null ) {
  // use the value of 'c' defined in <arch>.ad
  add(e);
} else {
  Expr *cost = new Expr(c);
  add(cost);
}
694}

696const char *Expr::compute_external(const Expr *c1, const Expr *c2) {
const char * result = NULL__null;

// Preserve use of external name which has a zero value
if( c1->_external_name != NULL__null ) {
  if( c2->is_zero() ) {
    snprintf(string_buffer, STRING_BUFFER_LENGTH2048, "%s", c1->as_string());
  } else {
    snprintf(string_buffer, STRING_BUFFER_LENGTH2048, "%s+%s", c1->as_string(), c2->as_string());
  }
  string_buffer[STRING_BUFFER_LENGTH2048 - 1] = '\0';
  result = strdup(string_buffer);
}
else if( c2->_external_name != NULL__null ) {
  if( c1->is_zero() ) {
    snprintf(string_buffer, STRING_BUFFER_LENGTH2048, "%s", c2->_external_name);
  } else {
    snprintf(string_buffer, STRING_BUFFER_LENGTH2048, "%s + %s", c1->as_string(), c2->as_string());
  }
  string_buffer[STRING_BUFFER_LENGTH2048 - 1] = '\0';
  result = strdup(string_buffer);
}
return result;
719}

721const char *Expr::compute_expr(const Expr *c1, const Expr *c2) {
if( !c1->is_zero() ) {
  if( c2->is_zero() ) {
    snprintf(string_buffer, STRING_BUFFER_LENGTH2048, "%s", c1->_expr);
  } else {
    snprintf(string_buffer, STRING_BUFFER_LENGTH2048, "%s+%s", c1->_expr, c2->_expr);
  }
}
else if( !c2->is_zero() ) {
  snprintf(string_buffer, STRING_BUFFER_LENGTH2048, "%s", c2->_expr);
}
else {
  sprintf( string_buffer, "0");
}
string_buffer[STRING_BUFFER_LENGTH2048 - 1] = '\0';
char *cost = strdup(string_buffer);

return cost;
739}

741int Expr::compute_min(const Expr *c1, const Expr *c2) {
int v1 = c1->_min_value;
int v2 = c2->_min_value;
assert(0 <= v2 && v2 <= Expr::Max, "sanity"){ if (!(0 <= v2 && v2 <= Expr::Max)) { fprintf(
stderr, "assert fails %s %d: %s\n", "/home/daniel/Projects/java/jdk/src/hotspot/share/adlc/dfa.cpp"
, 744, "sanity"); abort(); }};
assert(v1 <= Expr::Max - v2, "Invalid cost computation"){ if (!(v1 <= Expr::Max - v2)) { fprintf(stderr, "assert fails %s %d: %s\n"
, "/home/daniel/Projects/java/jdk/src/hotspot/share/adlc/dfa.cpp"
, 745, "Invalid cost computation"); abort(); }};

return v1 + v2;
748}


751int Expr::compute_max(const Expr *c1, const Expr *c2) {
int v1 = c1->_max_value;
int v2 = c2->_max_value;

// Check for overflow without producing UB. If v2 is positive
// and not larger than Max, the subtraction cannot underflow.
assert(0 <= v2 && v2 <= Expr::Max, "sanity"){ if (!(0 <= v2 && v2 <= Expr::Max)) { fprintf(
stderr, "assert fails %s %d: %s\n", "/home/daniel/Projects/java/jdk/src/hotspot/share/adlc/dfa.cpp"
, 757, "sanity"); abort(); }};
if (v1 > Expr::Max - v2) {
  return Expr::Max;
}

return v1 + v2;
763}

765void Expr::print() const {
if( _external_name != NULL__null ) {
  printf("  %s == (%s) === [%d, %d]\n", _external_name, _expr, _min_value, _max_value);
} else {
  printf("  %s === [%d, %d]\n", _expr, _min_value, _max_value);
}
771}

773void Expr::print_define(FILE *fp) const {
assert( _external_name != NULL, "definition does not have a name"){ if (!(_external_name != __null)) { fprintf(stderr, "assert fails %s %d: %s\n"
, "/home/daniel/Projects/java/jdk/src/hotspot/share/adlc/dfa.cpp"
, 774, "definition does not have a name"); abort(); }};
assert( _min_value == _max_value, "Expect user definitions to have constant value"){ if (!(_min_value == _max_value)) { fprintf(stderr, "assert fails %s %d: %s\n"
, "/home/daniel/Projects/java/jdk/src/hotspot/share/adlc/dfa.cpp"
, 775, "Expect user definitions to have constant value"); abort
(); }};
fprintf(fp, "#define  %s  (%s)  \n", _external_name, _expr);
fprintf(fp, "// value == %d \n", _min_value);
778}

780void Expr::print_assert(FILE *fp) const {
assert( _external_name != NULL, "definition does not have a name"){ if (!(_external_name != __null)) { fprintf(stderr, "assert fails %s %d: %s\n"
, "/home/daniel/Projects/java/jdk/src/hotspot/share/adlc/dfa.cpp"
, 781, "definition does not have a name"); abort(); }};
assert( _min_value == _max_value, "Expect user definitions to have constant value"){ if (!(_min_value == _max_value)) { fprintf(stderr, "assert fails %s %d: %s\n"
, "/home/daniel/Projects/java/jdk/src/hotspot/share/adlc/dfa.cpp"
, 782, "Expect user definitions to have constant value"); abort
(); }};
fprintf(fp, "  assert( %s == %d, \"Expect (%s) to equal %d\");\n", _external_name, _min_value, _expr, _min_value);
784}

786Expr *Expr::get_unknown() {
if( Expr::_unknown_expr == NULL__null ) {
  Expr::_unknown_expr = new Expr();
}

return Expr::_unknown_expr;
792}

794bool Expr::init_buffers() {
// Fill buffers with 0
for( int i = 0; i < STRING_BUFFER_LENGTH2048; ++i ) {
  external_buffer[i] = '\0';
  string_buffer[i]   = '\0';
}

return true;
802}

804bool Expr::check_buffers() {
// returns 'true' if buffer use may have overflowed
bool ok = true;
for( int i = STRING_BUFFER_LENGTH2048 - 100; i < STRING_BUFFER_LENGTH2048; ++i) {
  if( external_buffer[i] != '\0' || string_buffer[i]   != '\0' ) {
    ok = false;
    assert( false, "Expr:: Buffer overflow"){ if (!(false)) { fprintf(stderr, "assert fails %s %d: %s\n",
 "/home/daniel/Projects/java/jdk/src/hotspot/share/adlc/dfa.cpp"
, 810, "Expr:: Buffer overflow"); abort(); }};
  }
}

return ok;
815}


818//------------------------------ExprDict---------------------------------------
819// Constructor
820ExprDict::ExprDict( CmpKey cmp, Hash hash, Arena *arena )
: _expr(cmp, hash, arena), _defines()  {
822}
823ExprDict::~ExprDict() {
824}

826// Return # of name-Expr pairs in dict
827int ExprDict::Size(void) const {
return _expr.Size();
829}

831// define inserts the given key-value pair into the dictionary,
832// and records the name in order for later output, ...
833const Expr  *ExprDict::define(const char *name, Expr *expr) {
const Expr *old_expr = (*this)[name];
assert(old_expr == NULL, "Implementation does not support redefinition"){ if (!(old_expr == __null)) { fprintf(stderr, "assert fails %s %d: %s\n"
, "/home/daniel/Projects/java/jdk/src/hotspot/share/adlc/dfa.cpp"
, 835, "Implementation does not support redefinition"); abort
(); }};

_expr.Insert(name, expr);
_defines.addName(name);

return old_expr;
841}

843// Insert inserts the given key-value pair into the dictionary.  The prior
844// value of the key is returned; NULL if the key was not previously defined.
845const Expr  *ExprDict::Insert(const char *name, Expr *expr) {
return (Expr*)_expr.Insert((void*)name, (void*)expr);
847}

849// Finds the value of a given key; or NULL if not found.
850// The dictionary is NOT changed.
851const Expr  *ExprDict::operator [](const char *name) const {
return (Expr*)_expr[name];
853}

855void ExprDict::print_defines(FILE *fp) {
fprintf(fp, "\n");
const char *name = NULL__null;
for( _defines.reset(); (name = _defines.iter()) != NULL__null; ) {
  const Expr *expr = (const Expr*)_expr[name];
  assert( expr != NULL, "name in ExprDict without matching Expr in dictionary"){ if (!(expr != __null)) { fprintf(stderr, "assert fails %s %d: %s\n"
, "/home/daniel/Projects/java/jdk/src/hotspot/share/adlc/dfa.cpp"
, 860, "name in ExprDict without matching Expr in dictionary"
); abort(); }};
  expr->print_define(fp);
}
863}
864void ExprDict::print_asserts(FILE *fp) {
fprintf(fp, "\n");
fprintf(fp, "  // Following assertions generated from definition section\n");
const char *name = NULL__null;
for( _defines.reset(); (name = _defines.iter()) != NULL__null; ) {
  const Expr *expr = (const Expr*)_expr[name];
  assert( expr != NULL, "name in ExprDict without matching Expr in dictionary"){ if (!(expr != __null)) { fprintf(stderr, "assert fails %s %d: %s\n"
, "/home/daniel/Projects/java/jdk/src/hotspot/share/adlc/dfa.cpp"
, 870, "name in ExprDict without matching Expr in dictionary"
); abort(); }};
  expr->print_assert(fp);
}
873}

875// Print out the dictionary contents as key-value pairs
876static void dumpekey(const void* key)  { fprintf(stdoutstdout, "%s", (char*) key); }
877static void dumpexpr(const void* expr) { fflush(stdoutstdout); ((Expr*)expr)->print(); }

879void ExprDict::dump() {
_expr.print(dumpekey, dumpexpr);
881}


884//------------------------------ExprDict::private------------------------------
885// Disable public use of constructor, copy-ctor, operator =, operator ==
886ExprDict::ExprDict( ) : _expr(cmpkey,hashkey), _defines()  {
assert( false, "NotImplemented"){ if (!(false)) { fprintf(stderr, "assert fails %s %d: %s\n",
 "/home/daniel/Projects/java/jdk/src/hotspot/share/adlc/dfa.cpp"
, 887, "NotImplemented"); abort(); }};
888}
889ExprDict::ExprDict( const ExprDict & ) : _expr(cmpkey,hashkey), _defines() {
assert( false, "NotImplemented"){ if (!(false)) { fprintf(stderr, "assert fails %s %d: %s\n",
 "/home/daniel/Projects/java/jdk/src/hotspot/share/adlc/dfa.cpp"
, 890, "NotImplemented"); abort(); }};
891}
892ExprDict &ExprDict::operator =( const ExprDict &rhs) {
assert( false, "NotImplemented"){ if (!(false)) { fprintf(stderr, "assert fails %s %d: %s\n",
 "/home/daniel/Projects/java/jdk/src/hotspot/share/adlc/dfa.cpp"
, 893, "NotImplemented"); abort(); }};
_expr = rhs._expr;
return *this;
896}
897// == compares two dictionaries; they must have the same keys (their keys
898// must match using CmpKey) and they must have the same values (pointer
899// comparison).  If so 1 is returned, if not 0 is returned.
900bool ExprDict::operator ==(const ExprDict &d) const {
assert( false, "NotImplemented"){ if (!(false)) { fprintf(stderr, "assert fails %s %d: %s\n",
 "/home/daniel/Projects/java/jdk/src/hotspot/share/adlc/dfa.cpp"
, 901, "NotImplemented"); abort(); }};
return false;
903}


906//------------------------------Production-------------------------------------
907Production::Production(const char *result, const char *constraint, const char *valid) {
initialize();
_result     = result;
_constraint = constraint;
_valid      = valid;
912}

914void Production::initialize() {
_result     = NULL__null;
_constraint = NULL__null;
_valid      = knownInvalid;
_cost_lb    = Expr::get_unknown();
_cost_ub    = Expr::get_unknown();
920}

922void Production::print() {
printf("%s", (_result     == NULL__null ? "NULL" : _result ) );
printf("%s", (_constraint == NULL__null ? "NULL" : _constraint ) );
printf("%s", (_valid      == NULL__null ? "NULL" : _valid ) );
_cost_lb->print();
_cost_ub->print();
928}


931//------------------------------ProductionState--------------------------------
932void ProductionState::initialize() {
_constraint = noConstraint;

// reset each Production currently in the dictionary
DictI iter( &_production );
const void *x, *y = NULL__null;
for( ; iter.test(); ++iter) {
  x = iter._key;
  y = iter._value;
  Production *p = (Production*)y;
  if( p != NULL__null ) {
    p->initialize();
  }
}
946}

948Production *ProductionState::getProduction(const char *result) {
Production *p = (Production *)_production[result];
if( p == NULL__null ) {
  p = new Production(result, _constraint, knownInvalid);
  _production.Insert(result, p);
}

return p;
956}

958void ProductionState::set_constraint(const char *constraint) {
_constraint = constraint;
960}

962const char *ProductionState::valid(const char *result) {
return getProduction(result)->valid();
964}

966void ProductionState::set_valid(const char *result) {
Production *p = getProduction(result);

// Update valid as allowed by current constraints
if( _constraint == noConstraint ) {
  p->_valid = knownValid;
} else {
  if( p->_valid != knownValid ) {
    p->_valid = unknownValid;
  }
}
977}

979Expr *ProductionState::cost_lb(const char *result) {
return getProduction(result)->cost_lb();
981}

983Expr *ProductionState::cost_ub(const char *result) {
return getProduction(result)->cost_ub();
985}

987void ProductionState::set_cost_bounds(const char *result, const Expr *cost, bool has_state_check, bool has_cost_check) {
Production *p = getProduction(result);

if( p->_valid == knownInvalid ) {
  // Our cost bounds are not unknown, just not defined.
  p->_cost_lb = cost->clone();
  p->_cost_ub = cost->clone();
} else if (has_state_check || _constraint != noConstraint) {
  // The production is protected by a condition, so
  // the cost bounds may expand.
  // _cost_lb = min(cost, _cost_lb)
  if( cost->less_than_or_equal(p->_cost_lb) ) {
    p->_cost_lb = cost->clone();
  }
  // _cost_ub = max(cost, _cost_ub)
  if( p->_cost_ub->less_than_or_equal(cost) ) {
    p->_cost_ub = cost->clone();
  }
} else if (has_cost_check) {
  // The production has no condition check, but does
  // have a cost check that could reduce the upper
  // and/or lower bound.
  // _cost_lb = min(cost, _cost_lb)
  if( cost->less_than_or_equal(p->_cost_lb) ) {
    p->_cost_lb = cost->clone();
  }
  // _cost_ub = min(cost, _cost_ub)
  if( cost->less_than_or_equal(p->_cost_ub) ) {
    p->_cost_ub = cost->clone();
  }
} else {
  // The costs are unconditionally set.
  p->_cost_lb = cost->clone();
  p->_cost_ub = cost->clone();
}

1023}

1025// Print out the dictionary contents as key-value pairs
1026static void print_key (const void* key)              { fprintf(stdoutstdout, "%s", (char*) key); }
1027static void print_production(const void* production) { fflush(stdoutstdout); ((Production*)production)->print(); }

1029void ProductionState::print() {
_production.print(print_key, print_production);
1031}