Skip to main content
Redhat Developers  Logo
  • Products

    Featured

    • Red Hat Enterprise Linux
      Red Hat Enterprise Linux Icon
    • Red Hat OpenShift AI
      Red Hat OpenShift AI
    • Red Hat Enterprise Linux AI
      Linux icon inside of a brain
    • Image mode for Red Hat Enterprise Linux
      RHEL image mode
    • Red Hat OpenShift
      Openshift icon
    • Red Hat Ansible Automation Platform
      Ansible icon
    • Red Hat Developer Hub
      Developer Hub
    • View All Red Hat Products
    • Linux

      • Red Hat Enterprise Linux
      • Image mode for Red Hat Enterprise Linux
      • Red Hat Universal Base Images (UBI)
    • Java runtimes & frameworks

      • JBoss Enterprise Application Platform
      • Red Hat build of OpenJDK
    • Kubernetes

      • Red Hat OpenShift
      • Microsoft Azure Red Hat OpenShift
      • Red Hat OpenShift Virtualization
      • Red Hat OpenShift Lightspeed
    • Integration & App Connectivity

      • Red Hat Build of Apache Camel
      • Red Hat Service Interconnect
      • Red Hat Connectivity Link
    • AI/ML

      • Red Hat OpenShift AI
      • Red Hat Enterprise Linux AI
    • Automation

      • Red Hat Ansible Automation Platform
      • Red Hat Ansible Lightspeed
    • Developer tools

      • Red Hat Trusted Software Supply Chain
      • Podman Desktop
      • Red Hat OpenShift Dev Spaces
    • Developer Sandbox

      Developer Sandbox
      Try Red Hat products and technologies without setup or configuration fees for 30 days with this shared Openshift and Kubernetes cluster.
    • Try at no cost
  • Technologies

    Featured

    • AI/ML
      AI/ML Icon
    • Linux
      Linux Icon
    • Kubernetes
      Cloud icon
    • Automation
      Automation Icon showing arrows moving in a circle around a gear
    • View All Technologies
    • Programming Languages & Frameworks

      • Java
      • Python
      • JavaScript
    • System Design & Architecture

      • Red Hat architecture and design patterns
      • Microservices
      • Event-Driven Architecture
      • Databases
    • Developer Productivity

      • Developer productivity
      • Developer Tools
      • GitOps
    • Secure Development & Architectures

      • Security
      • Secure coding
    • Platform Engineering

      • DevOps
      • DevSecOps
      • Ansible automation for applications and services
    • Automated Data Processing

      • AI/ML
      • Data Science
      • Apache Kafka on Kubernetes
      • View All Technologies
    • Start exploring in the Developer Sandbox for free

      sandbox graphic
      Try Red Hat's products and technologies without setup or configuration.
    • Try at no cost
  • Learn

    Featured

    • Kubernetes & Cloud Native
      Openshift icon
    • Linux
      Rhel icon
    • Automation
      Ansible cloud icon
    • Java
      Java icon
    • AI/ML
      AI/ML Icon
    • View All Learning Resources

    E-Books

    • GitOps Cookbook
    • Podman in Action
    • Kubernetes Operators
    • The Path to GitOps
    • View All E-books

    Cheat Sheets

    • Linux Commands
    • Bash Commands
    • Git
    • systemd Commands
    • View All Cheat Sheets

    Documentation

    • API Catalog
    • Product Documentation
    • Legacy Documentation
    • Red Hat Learning

      Learning image
      Boost your technical skills to expert-level with the help of interactive lessons offered by various Red Hat Learning programs.
    • Explore Red Hat Learning
  • Developer Sandbox

    Developer Sandbox

    • Access Red Hat’s products and technologies without setup or configuration, and start developing quicker than ever before with our new, no-cost sandbox environments.
    • Explore Developer Sandbox

    Featured Developer Sandbox activities

    • Get started with your Developer Sandbox
    • OpenShift virtualization and application modernization using the Developer Sandbox
    • Explore all Developer Sandbox activities

    Ready to start developing apps?

    • Try at no cost
  • Blog
  • Events
  • Videos

Value range propagation in GCC with Project Ranger

April 28, 2021
Andrew MacLeod
Related topics:
C, C#, C++Linux
Related products:
Red Hat Enterprise Linux

Share:

    One of the optimizations GNU Compiler Collection (GCC) performs on C and C++ programs is value range propagation (VRP). VRP determines what subranges a variable can contain and uses that information to eliminate redundant calculations. This in turn makes programs smaller and run faster.

    As a simple example, consider the two nested if statements in the following C snippet:

    if (a < 100 && b < 100)
      {
        c = a + b;
        if (c < 200)
          foo (c);
      }

    We know that, if the outer if statement runs its block, a + b cannot be larger than 99 + 99, or 198. This means we don’t need to check if (c < 200) and can rewrite the snippet to be simply:

    if (a < 100 && b < 100)
      foo (a + b);

    Branches are expensive in programs, so this sort of thing is a big deal. It's an even bigger deal in the modern world where we are concerned about security issues like buffer overflows (accessing data outside of expected bounds). The compiler may add range checks or do other verification to harden the code, but this comes at a cost. VRP can determine that some of those checks are not needed. This produces a faster program that is still safe. We can also use range information to identify dangerous segments of code and alert the user with a warning. The list of potential uses for VRP regularly grows.

    The initial version of VRP in GCC was created in 2006 when static single assignment (SSA) was a new infrastructure in the compiler. With a renewed interest in utilizing range information, GCC’s original version of VRP simply isn't flexible enough. Numerous improvements have been made over the past decade, but there is still a long list of outstanding change requests. The underlying infrastructure simply has too many shortcomings to address current needs. The oldest request originates in 2007!

    Enter Project Ranger

    We’ve been working on Project Ranger for more than three years now. It is designed from the ground up to resolve all the outstanding issues and replace the current VRP pass. Other passes in the compiler will also be able to access this range information. This upgrade is not without difficulties, as anyone who has tried to revamp a 30-year-old codebase may have experienced. An earlier article covers some of the new technology in this project.

    GCC 10 (the current release) contains an object-oriented replacement for the underlying range calculations we call range-ops. Range-ops is responsible for solving various kinds of range equations based on each statement. It is also pre-wired to support a new representation of ranges. Range-ops was the first stage of Ranger to make it into GCC. This stage has been live for almost a year and continues to perform well.

    The upcoming GCC 11 release will contain:

    • A new implementation of ranges that allows more precise representation.
    • A new Ranger VRP infrastructure that can make use of these precise ranges.
    • A hybrid VRP pass for this release only, which contains both the original and the new version of VRP.

    A couple of other passes are also utilizing Project Ranger to provide some combination of improved speed and better results.

    Why is there a hybrid pass?

    Development of Project Ranger will continue into GCC 12, where we expect to see the project fully realized. Without the full suite of features, we cannot fully replace the original VRP pass.

    The hybrid pass queries both the original and the new VRP engines and combines the results. This hybrid pass helps us optimize everything we used to do, as well as getting some new opportunities. It also allows us to easily track differences between the old and new approaches. Not to worry—the hybrid pass is still quite fast.

    The primary missing component is relation processing. The initial example in this article showed how ranges can be used to remove conditions. There are times when a relationship between operands must be known in order to remove the condition. An example follows:

    if (a == b)
      if (b == c)
        if (a < c) // This can never be true
          call (b)

    The final if condition is always false, but we can't determine that based on ranges alone. There might be no discernible ranges for any of these variables. To detect the value of the expression, we need to introduce a thorough knowledge of relations. If we know that a == b and b == c, we can also conclude that a == c, and therefore a < c can never be true. It seems easy and obvious, but it is not quite so natural in the compiler.

    The original version of VRP has numerous ad-hoc additions that allow it to perform this optimization sometimes. This is why GCC 11 has a hybrid pass. These important optimizations can still be performed while benefiting from the other features Ranger provides. We also get a full release cycle to compare the new version to the old one and ensure we miss nothing.

    This new relation processing code is ready for the start of the GCC 12 development cycle. We are leveraging the new range-ops infrastructure to also evaluate relationships. This enhancement will allow any kind of statement that may calculate a range to also provide relationships between operands:

    a = b + 2    // Establishes a > b
    if (a < b)   // We can fold this away since it can never be true

    We can conclude that a > b after the addition, and eliminate the if statement. We expect to expose and exploit a lot more of these implied relationships in GCC 12.

    Into the future

    Project Ranger should be the only VRP implementation required in GCC 12. We can remove the legacy code and the various compatibility layers it required. This will improve compilation speed as well as reduce maintenance effort. Finally, we expect there will be additional passes making use of the more precise ranges that are easily available.

    Building on this into the future, we also have plans for:

    • Handling ranges for types other than integral values (floats, complex numbers, etc.).
    • Bit value tracking (known 0 and 1 bits).
    • Additional passes making use of this infrastructure.
    • Continued improvement in memory usage and compilation speed.

    You may not be able to tell when you compile a program, but there certainly is a lot of new work going on under the covers. GCC 11 has some range improvements, but we hope to resolve most, if not all, of the 26 outstanding deficiencies and feature requests when GCC 12 comes out.

    Last updated: February 11, 2024

    Recent Posts

    • How to run a fraud detection AI model on RHEL CVMs

    • How we use software provenance at Red Hat

    • Alternatives to creating bootc images from scratch

    • How to update OpenStack Services on OpenShift

    • How to integrate vLLM inference into your macOS and iOS apps

    Red Hat Developers logo LinkedIn YouTube Twitter Facebook

    Products

    • Red Hat Enterprise Linux
    • Red Hat OpenShift
    • Red Hat Ansible Automation Platform

    Build

    • Developer Sandbox
    • Developer Tools
    • Interactive Tutorials
    • API Catalog

    Quicklinks

    • Learning Resources
    • E-books
    • Cheat Sheets
    • Blog
    • Events
    • Newsletter

    Communicate

    • About us
    • Contact sales
    • Find a partner
    • Report a website issue
    • Site Status Dashboard
    • Report a security problem

    RED HAT DEVELOPER

    Build here. Go anywhere.

    We serve the builders. The problem solvers who create careers with code.

    Join us if you’re a developer, software engineer, web designer, front-end designer, UX designer, computer scientist, architect, tester, product manager, project manager or team lead.

    Sign me up

    Red Hat legal and privacy links

    • About Red Hat
    • Jobs
    • Events
    • Locations
    • Contact Red Hat
    • Red Hat Blog
    • Inclusion at Red Hat
    • Cool Stuff Store
    • Red Hat Summit

    Red Hat legal and privacy links

    • Privacy statement
    • Terms of use
    • All policies and guidelines
    • Digital accessibility

    Report a website issue