Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===-- InstructionPrecedenceTracking.h -------------------------*- C++ -*-===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

// Implements a class that is able to define some instructions as "special"

// (e.g. as having implicit control flow, or writing memory, or having another

// interesting property) and then efficiently answers queries of the types:

// 1. Are there any special instructions in the block of interest?

// 2. Return first of the special instructions in the given block;

// 3. Check if the given instruction is preceeded by the first special

//    instruction in the same block.

// The class provides caching that allows to answer these queries quickly. The

// user must make sure that the cached data is invalidated properly whenever

// a content of some tracked block is changed.

//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H

#define LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H

#include "llvm/ADT/DenseMap.h"

namespace llvm {

class BasicBlock;

class Instruction;

class InstructionPrecedenceTracking {

  // Maps a block to the topmost special instruction in it. If the value is

  // nullptr, it means that it is known that this block does not contain any

  // special instructions.

  DenseMap<const BasicBlock *, const Instruction *> FirstSpecialInsts;

  // Fills information about the given block's special instructions.

  void fill(const BasicBlock *BB);

#ifndef NDEBUG

  /// Asserts that the cached info for \p BB is up-to-date. This helps to catch

  /// the usage error of accessing a block without properly invalidating after a

  /// previous transform.

  void validate(const BasicBlock *BB) const;

  /// Asserts whether or not the contents of this tracking is up-to-date. This

  /// helps to catch the usage error of accessing a block without properly

  /// invalidating after a previous transform.

  void validateAll() const;

#endif

protected:

  /// Returns the topmost special instruction from the block \p BB. Returns

  /// nullptr if there is no special instructions in the block.

  const Instruction *getFirstSpecialInstruction(const BasicBlock *BB);

  /// Returns true iff at least one instruction from the basic block \p BB is

  /// special.

  bool hasSpecialInstructions(const BasicBlock *BB);

  /// Returns true iff the first special instruction of \p Insn's block exists

  /// and dominates \p Insn.

  bool isPreceededBySpecialInstruction(const Instruction *Insn);

  /// A predicate that defines whether or not the instruction \p Insn is

  /// considered special and needs to be tracked. Implementing this method in

  /// children classes allows to implement tracking of implicit control flow,

  /// memory writing instructions or any other kinds of instructions we might

  /// be interested in.

  virtual bool isSpecialInstruction(const Instruction *Insn) const = 0;

  virtual ~InstructionPrecedenceTracking() = default;

public:

  /// Notifies this tracking that we are going to insert a new instruction \p

  /// Inst to the basic block \p BB. It makes all necessary updates to internal

  /// caches to keep them consistent.

  void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB);

  /// Notifies this tracking that we are going to remove the instruction \p Inst

  /// It makes all necessary updates to internal caches to keep them consistent.

  void removeInstruction(const Instruction *Inst);

  /// Notifies this tracking that we are going to replace all uses of \p Inst.

  /// It makes all necessary updates to internal caches to keep them consistent.

  /// Should typically be called before a RAUW.

  void removeUsersOf(const Instruction *Inst);

  /// Invalidates all information from this tracking.

  void clear();

};

/// This class allows to keep track on instructions with implicit control flow.

/// These are instructions that may not pass execution to their successors. For

/// example, throwing calls and guards do not always do this. If we need to know

/// for sure that some instruction is guaranteed to execute if the given block

/// is reached, then we need to make sure that there is no implicit control flow

/// instruction (ICFI) preceding it. For example, this check is required if we

/// perform PRE moving non-speculable instruction to other place.

class ImplicitControlFlowTracking : public InstructionPrecedenceTracking {

public:

  /// Returns the topmost instruction with implicit control flow from the given

  /// basic block. Returns nullptr if there is no such instructions in the block.

  const Instruction *getFirstICFI(const BasicBlock *BB) {

    return getFirstSpecialInstruction(BB);

  }

  /// Returns true if at least one instruction from the given basic block has

  /// implicit control flow.

  bool hasICF(const BasicBlock *BB) {

    return hasSpecialInstructions(BB);

  }

  /// Returns true if the first ICFI of Insn's block exists and dominates Insn.

  bool isDominatedByICFIFromSameBlock(const Instruction *Insn) {

    return isPreceededBySpecialInstruction(Insn);

  }

  bool isSpecialInstruction(const Instruction *Insn) const override;

};

class MemoryWriteTracking : public InstructionPrecedenceTracking {

public:

  /// Returns the topmost instruction that may write memory from the given

  /// basic block. Returns nullptr if there is no such instructions in the block.

  const Instruction *getFirstMemoryWrite(const BasicBlock *BB) {

    return getFirstSpecialInstruction(BB);

  }

  /// Returns true if at least one instruction from the given basic block may

  /// write memory.

  bool mayWriteToMemory(const BasicBlock *BB) {

    return hasSpecialInstructions(BB);

  }

  /// Returns true if the first memory writing instruction of Insn's block

  /// exists and dominates Insn.

  bool isDominatedByMemoryWriteFromSameBlock(const Instruction *Insn) {

    return isPreceededBySpecialInstruction(Insn);

  }

  bool isSpecialInstruction(const Instruction *Insn) const override;

};

} // llvm

#endif // LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H