https://gcc.gnu.org/g:49dec4fef16e51a231af08f4bc7353459cd3951b
commit r16-6790-g49dec4fef16e51a231af08f4bc7353459cd3951b Author: Kugan Vivekanandarajah <[email protected]> Date: Thu Jan 15 14:36:44 2026 +1100 [Autofdo] Add hierarchical discriminator support This patch introduces the basic infrastructure for hierarchical discriminators with format [Base:8][Multiplicity:7][CopyID:11][Unused:6]. It adds helper functions to create and extract discriminator components. gcc/ChangeLog: * Makefile.in: Add hierarchical_discriminator.o to OBJS. * hierarchical_discriminator.cc: New file. * hierarchical_discriminator.h: New file. * function.h (copyid_alloc): New. * input.cc (location_with_discriminator_components): New function. (get_discriminator_components_from_loc): Likewise. * input.h (DISCR_BASE_BITS): New constant. (DISCR_MULTIPLICITY_BITS): Likewise. (DISCR_COPYID_BITS): Likewise. (DISCR_UNUSED_BITS): Likewise. (DISCR_BASE_MASK): Likewise. (DISCR_MULTIPLICITY_MASK): Likewise. (DISCR_COPYID_MASK): Likewise. (DISCR_BASE_SHIFT): Likewise. (DISCR_MULTIPLICITY_SHIFT): Likewise. (DISCR_COPYID_SHIFT): Likewise. (DISCR_BASE_MAX): Likewise. (DISCR_MULTIPLICITY_MAX): Likewise. (DISCR_COPYID_MAX): Likewise. (location_with_discriminator_components): New function declaration. (get_discriminator_components_from_loc): Likewise. Signed-off-by: Kugan Vivekanandarajah <[email protected]> Diff: --- gcc/Makefile.in | 1 + gcc/function.h | 5 + gcc/hierarchical_discriminator.cc | 264 ++++++++++++++++++++++++++++++++++++++ gcc/hierarchical_discriminator.h | 93 ++++++++++++++ gcc/input.cc | 29 +++++ gcc/input.h | 43 +++++++ 6 files changed, 435 insertions(+) diff --git a/gcc/Makefile.in b/gcc/Makefile.in index b41cf5df849f..abf98aabac83 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1464,6 +1464,7 @@ OBJS = \ dce.o \ ddg.o \ debug.o \ + hierarchical_discriminator.o \ dep-fusion.o \ df-core.o \ df-problems.o \ diff --git a/gcc/function.h b/gcc/function.h index 3190f6e990ca..765c71309fac 100644 --- a/gcc/function.h +++ b/gcc/function.h @@ -274,6 +274,11 @@ struct GTY(()) function { the same uid. This is used for condition coverage. */ hash_map <gcond*, unsigned> *GTY((skip)) cond_uids; + /* Per-function copyid allocator for hierarchical discriminators. + Tracks the next available copyid for each location to ensure uniqueness + across code duplication passes (unrolling, vectorization, etc.). */ + struct copyid_allocator *GTY((skip)) copyid_alloc; + /* For function.cc. */ /* Points to the FUNCTION_DECL of this function. */ diff --git a/gcc/hierarchical_discriminator.cc b/gcc/hierarchical_discriminator.cc new file mode 100644 index 000000000000..734da65c29d3 --- /dev/null +++ b/gcc/hierarchical_discriminator.cc @@ -0,0 +1,264 @@ +/* Copyright The GNU Toolchain Authors + +This file is part of GCC. + +GCC 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 3, or (at your option) any later +version. + +GCC 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 GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "tree.h" +#include "gimple.h" +#include "tree-pass.h" +#include "ssa.h" +#include "gimple-iterator.h" +#include "tree-cfg.h" +#include "cfgloop.h" +#include "hierarchical_discriminator.h" +#include "cfghooks.h" +#include "diagnostic-core.h" +#include "function.h" +#include "rtl.h" +#include "basic-block.h" + +/* Helper to update a location with new discriminator components. If + multiplicity_factor is non-zero, multiply existing multiplicity. + If copyid is non-zero, set it (otherwise preserve existing). */ + +static location_t +update_location_discriminator (location_t loc, + unsigned int multiplicity_factor, + unsigned int copyid) +{ + if (loc == UNKNOWN_LOCATION) + return loc; + + discriminator_components comp = get_discriminator_components_from_loc (loc); + + /* Multiply existing multiplicity if requested. */ + if (multiplicity_factor > 0) + { + unsigned int new_mult = (comp.multiplicity == 0) + ? multiplicity_factor + : comp.multiplicity * multiplicity_factor; + if (new_mult > DISCR_MULTIPLICITY_MAX) + new_mult = DISCR_MULTIPLICITY_MAX; + comp.multiplicity = new_mult; + } + + /* Update copyid if requested. */ + if (copyid > 0) + comp.copyid = copyid; + + return location_with_discriminator_components (loc, comp); +} + +/* Assign discriminators to a statement + Updates the multiplicity and/or copyid discriminator components for + all statements in the given basic block, while preserving the base + discriminator. + + If multiplicity_factor > 0, multiply existing multiplicity by this factor. + If copyid > 0, set it to this value. */ + +void +assign_discriminators_to_stmt (gimple* stmt, + unsigned int multiplicity_factor, + unsigned int copyid) +{ + location_t loc = gimple_location (stmt); + + if (loc != UNKNOWN_LOCATION) + { + location_t new_loc + = update_location_discriminator (loc, + multiplicity_factor, + copyid); + gimple_set_location (stmt, new_loc); + } +} + + +/* Assign discriminators to all statements in a basic block. This + function updates the multiplicity and/or copyid discriminator components for + all statements in the given basic block, while preserving the base + discriminator. + + If multiplicity_factor > 0, multiply existing multiplicity by this factor. + If copyid > 0, set it to this value. */ + +void +assign_discriminators_to_bb (basic_block bb, + unsigned int multiplicity_factor, + unsigned int copyid) +{ + gimple_stmt_iterator gsi; + gphi_iterator phi_gsi; + edge e; + edge_iterator ei; + + /* Update PHI statements. */ + for (phi_gsi = gsi_start_phis (bb); !gsi_end_p (phi_gsi); + gsi_next (&phi_gsi)) + { + gphi *phi = phi_gsi.phi (); + location_t loc = gimple_location (phi); + + if (loc != UNKNOWN_LOCATION) + { + location_t new_loc + = update_location_discriminator (loc, + multiplicity_factor, + copyid); + gimple_set_location (phi, new_loc); + } + } + + /* Update regular statements. */ + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple *stmt = gsi_stmt (gsi); + + if (is_gimple_debug (stmt)) + continue; + + location_t loc = gimple_location (stmt); + if (loc != UNKNOWN_LOCATION) + { + location_t new_loc + = update_location_discriminator (loc, + multiplicity_factor, + copyid); + gimple_set_location (stmt, new_loc); + } + } + + /* Update goto/edge locations. */ + FOR_EACH_EDGE (e, ei, bb->succs) + { + location_t loc = e->goto_locus; + if (loc != UNKNOWN_LOCATION) + { + location_t new_loc + = update_location_discriminator (loc, + multiplicity_factor, + copyid); + e->goto_locus = new_loc; + } + } +} + +/* Assign discriminators to all basic blocks in a loop. This function is + used by loop versioning passes to assign version IDs and vectorization + factors to all statements in a loop version. */ + +void +assign_discriminators_to_loop (class loop *loop, + unsigned int multiplicity_factor, + unsigned int copyid) +{ + basic_block *bbs; + unsigned int i; + + /* Get all basic blocks in the loop. */ + bbs = get_loop_body (loop); + + /* Assign discriminators to all blocks in the loop. */ + for (i = 0; i < loop->num_nodes; i++) + assign_discriminators_to_bb (bbs[i], multiplicity_factor, copyid); + + free (bbs); +} + + +/* Initialize the per-function copyid allocator. */ + +static void +init_copyid_allocator (struct function *fn) +{ + if (!fn) + return; + + if (fn->copyid_alloc) + return; /* Already initialized. */ + + fn->copyid_alloc = XNEW (struct copyid_allocator); + fn->copyid_alloc->location_map + = new hash_map<int_hash<location_t, UNKNOWN_LOCATION, UNKNOWN_LOCATION>, + unsigned int>; + fn->copyid_alloc->initialized = true; +} + +/* Allocate a unique copy_id base for the given location. + STRIDE indicates how many copy_ids to reserve (for unrolling N times, + use stride=N). Returns the base copy_id. */ + +unsigned int +allocate_copyid_base (location_t loc, unsigned int stride) +{ + /* Need current function context. */ + if (!cfun) + return 1; /* No function context, return default. */ + + init_copyid_allocator (cfun); + + loc = get_pure_location (loc); + + /* Cannot allocate copyid for unknown location. */ + if (loc == UNKNOWN_LOCATION) + return 1; /* Return default base copyid. */ + + /* Check if this location has been seen before. */ + unsigned int *existing = cfun->copyid_alloc->location_map->get (loc); + if (existing) + { + /* Location already duplicated before. Allocate next copy_id for it. */ + unsigned int base = *existing; + *existing += stride; /* Update for next duplication. */ + + /* Clamp to maximum. */ + if (*existing > DISCR_COPYID_MAX) + *existing = DISCR_COPYID_MAX; + return base; + } + else + { + /* First duplication at this location in this function. + Start at 1 (not 0, which means "no copyid"). */ + unsigned int base = 1; + unsigned int next = base + stride; + if (next > DISCR_COPYID_MAX) + next = DISCR_COPYID_MAX; + /* Record this location for future duplications. */ + cfun->copyid_alloc->location_map->put (loc, next); + + return base; + } +} + +/* Free the copy_id allocator for a function. Called when the function + is being destroyed. */ + +void +free_copyid_allocator (struct function *fn) +{ + if (fn && fn->copyid_alloc) + { + delete fn->copyid_alloc->location_map; + XDELETE (fn->copyid_alloc); + fn->copyid_alloc = NULL; + } +} diff --git a/gcc/hierarchical_discriminator.h b/gcc/hierarchical_discriminator.h new file mode 100644 index 000000000000..de8c6a19b722 --- /dev/null +++ b/gcc/hierarchical_discriminator.h @@ -0,0 +1,93 @@ +/* Copyright The GNU Toolchain Authors + +This file is part of GCC. + +GCC 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 3, or (at your option) any later +version. + +GCC 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 GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#ifndef GCC_HIERARCHICAL_DISCRIMINATOR_H +#define GCC_HIERARCHICAL_DISCRIMINATOR_H + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "gimple.h" +#include "tree.h" +#include "basic-block.h" +#include "input.h" + +/* Hierarchical discriminator layout (32 bits total): + Discriminator format: [Base:8][Multiplicity:7][CopyID:11][Unused:6] + - Base: bits 0-7 (8 bits, 0-255) + - Multiplicity: bits 8-14 (7 bits, 0-127) + - CopyID: bits 15-25 (11 bits, 0-2047) + - Unused: bits 26-31 (6 bits, reserved) + + Base discriminator: Used by front-end and early passes to distinguish + different statements on the same source line. + + Multiplicity: Represents when a single IR statement corresponds to + multiple scalar iterations or executions + + CopyID: Unique identifier for distinct code copies to distinguish + */ + + +/* Helper function to assign discriminators to a statement. + This preserves the base discriminator and updates multiplicity + and/or copyid. */ +extern void assign_discriminators_to_stmt (gimple* stmt, + unsigned int multiplicity_factor, + unsigned int copyid); + +/* Helper function to assign discriminators to all statements in a basic + block. This preserves the base discriminator and updates multiplicity + and/or copyid. PHI statements, PHI arguments, and edge locations are + also updated. */ +extern void assign_discriminators_to_bb (basic_block bb, + unsigned int multiplicity_factor, + unsigned int copyid); + +/* Helper function to assign discriminators to all basic blocks in a loop. + This is used by loop versioning passes to distinguish different versions + of the same loop and to indicate vectorization factors. */ +extern void assign_discriminators_to_loop (class loop *loop, + unsigned int multiplicity_factor, + unsigned int copyid); + +/* Copy ID allocator for tracking unique copy_id assignments per location. + This ensures that nested code duplication (e.g., unroll + vectorize) gets + unique copy_ids even when the same location is duplicated + multiple times. */ + +struct copyid_allocator +{ + /* Hash map from location to the next available copy_id base. + Key: location_t, Value: unsigned int (next available base). */ + hash_map<int_hash<location_t, UNKNOWN_LOCATION, UNKNOWN_LOCATION>, + unsigned int> *location_map; + + /* Whether the allocator has been initialized. */ + bool initialized; +}; + +/* Allocate a unique copy_id base for the given location. + STRIDE indicates how many copy_ids to reserve (for unrolling N times, + use stride=N). Returns the base copy_id. */ +extern unsigned int allocate_copyid_base (location_t loc, unsigned int stride); + +/* Free the copy_id allocator for a function. */ +extern void free_copyid_allocator (struct function *fn); + +#endif /* GCC_HIERARCHICAL_DISCRIMINATOR_H. */ diff --git a/gcc/input.cc b/gcc/input.cc index bd216a2821ca..1ef3c5fdb5b7 100644 --- a/gcc/input.cc +++ b/gcc/input.cc @@ -1074,6 +1074,35 @@ get_discriminator_from_loc (location_t locus) return get_discriminator_from_loc (line_table, locus); } +/* Create a location with hierarchical discriminator components. */ + +location_t +location_with_discriminator_components (location_t locus, + const discriminator_components &comp) +{ + gcc_assert (comp.base <= DISCR_BASE_MAX); + gcc_assert (comp.multiplicity <= DISCR_MULTIPLICITY_MAX); + gcc_assert (comp.copyid <= DISCR_COPYID_MAX); + unsigned int discriminator = (comp.base << DISCR_BASE_SHIFT) + | (comp.multiplicity << DISCR_MULTIPLICITY_SHIFT) + | (comp.copyid << DISCR_COPYID_SHIFT); + return location_with_discriminator (locus, discriminator); +} + +/* Get hierarchical discriminator components from a location. */ + +discriminator_components +get_discriminator_components_from_loc (location_t locus) +{ + unsigned int discriminator = get_discriminator_from_loc (locus); + discriminator_components comp; + comp.base = discriminator & DISCR_BASE_MASK; + comp.multiplicity = (discriminator >> DISCR_MULTIPLICITY_SHIFT) + & DISCR_MULTIPLICITY_MASK; + comp.copyid = (discriminator >> DISCR_COPYID_SHIFT) & DISCR_COPYID_MASK; + return comp; +} + #if CHECKING_P namespace selftest { diff --git a/gcc/input.h b/gcc/input.h index 0b49c249c13b..f6aeff9db37d 100644 --- a/gcc/input.h +++ b/gcc/input.h @@ -89,6 +89,49 @@ extern location_t location_with_discriminator (location_t, int); extern bool has_discriminator (location_t); extern int get_discriminator_from_loc (location_t); +/* Hierarchical discriminator support for AutoFDO. +Discriminator format: [Base:8][Multiplicity:7][CopyID:11][Unused:6] +- Base discriminator (bits 0-7): Distinguishes instructions at same line +- Multiplicity (bits 8-14): Duplication factor for unrolling/vectorization +- CopyID (bits 15-25): Unique identifier for code copies +- Unused (bits 26-31): Reserved. */ + +/* Discriminator bit layout constants. */ +#define DISCR_BASE_BITS 8 +#define DISCR_MULTIPLICITY_BITS 7 +#define DISCR_COPYID_BITS 11 +#define DISCR_UNUSED_BITS 6 + +#define DISCR_BASE_MASK ((1u << DISCR_BASE_BITS) - 1) +#define DISCR_MULTIPLICITY_MASK ((1u << DISCR_MULTIPLICITY_BITS) - 1) +#define DISCR_COPYID_MASK ((1u << DISCR_COPYID_BITS) - 1) + +#define DISCR_BASE_SHIFT 0 +#define DISCR_MULTIPLICITY_SHIFT DISCR_BASE_BITS +#define DISCR_COPYID_SHIFT (DISCR_BASE_BITS + DISCR_MULTIPLICITY_BITS) + +/* Maximum values for each discriminator field. */ +#define DISCR_BASE_MAX DISCR_BASE_MASK +#define DISCR_MULTIPLICITY_MAX DISCR_MULTIPLICITY_MASK +#define DISCR_COPYID_MAX DISCR_COPYID_MASK + +/* Structure to hold hierarchical discriminator components. */ +struct discriminator_components +{ + unsigned int base; /* Front-end discriminator (bits 0-7). */ + unsigned int multiplicity; /* Duplication factor (bits 8-14). */ + unsigned int copyid; /* Copy identifier (bits 15-25). */ +}; + +/* Create location with hierarchical discriminator. */ +extern location_t +location_with_discriminator_components (location_t, + const discriminator_components &); + +/* Get discriminator components from location. */ +extern discriminator_components +get_discriminator_components_from_loc (location_t); + #define LOCATION_FILE(LOC) ((expand_location (LOC)).file) #define LOCATION_LINE(LOC) ((expand_location (LOC)).line) #define LOCATION_COLUMN(LOC)((expand_location (LOC)).column)
