[IR] Add token types

[majnemer]

Summary

This introduces the basic functionality to support "token types".
The motivation stems from the need to perform operations on a Value
whose provenance cannot be obscured.

There are several applications for such a type but my immediate
motivation stems from WinEH. Our personality routine enforces a
single-entry - single-exit regime for cleanups. After several rounds of
optimizations, we may be left with a terminator whose "cleanup-entry
block" is not entirely clear because control flow has merged two
cleanups together. We have experimented with using labels as operands
inside of instructions which are not terminators to indicate where we
came from but found that LLVM does not expect such exotic uses of
BasicBlocks.

Instead, we can use this new type to clearly associate the "entry point"
and "exit point" of our cleanup. This is done by having the cleanuppad
yield a Token and consuming it at the cleanupret.
The token type makes it impossible to obscure or otherwise hide the
Value, making it trivial to track the relationship between the two
points.

What is the burden to the optimizer? Well, it turns out we have already
paid down this cost by accepting that there are certain calls that we
are not permitted to duplicate, optimizations have to watch out for
such instructions anyway. There are additional places in the optimizer
that we will probably have to update but early examination has given me
the impression that this will not be heroic.

[silvas]

+John McCall

[JosephTremoulet]

LGTM aside from some questions about the return type exclusion.

lib/IR/Type.cpp

383

Will this preclude having intrinsics that produce tokens? I'd have thought such a thing would make sense, though I don't have an immediate need for one.

test/Assembler/token.ll

7

Seems odd to allow token parameters but not token returns; I'd have expected each kind of cross-function transfer to cause roughly the same amount of trouble.

[rnk]

Can you expand on the use cases for tokens? It sounded like there were more than just this on Friday.

Fundamentally, this is breaking the invariant that values produced by instructions Can Be Phied. We need more than one use case to want to break that rule.

lib/Transforms/Utils/SimplifyCFG.cpp

1644–1645

Shouldn't this have a test?

test/Verifier/token1.ll

9

I think you can combine these tests into one token-invalid.ll file. You get one verifier failure per function, so if you keep them split up like this, it'll work.

[majnemer]

In D11861#220538, @rnk wrote:

Can you expand on the use cases for tokens? It sounded like there were more than just this on Friday.

Fundamentally, this is breaking the invariant that values produced by instructions Can Be Phied. We need more than one use case to want to break that rule.

The folks working on safepoints need something along these lines in order to correctly track pointer provenance. @sanjoy or @reames could probably do a better job describing the role of token types in "argument bundles".

lib/IR/Type.cpp

383

We can always loosen the restriction later if we need to.

lib/Transforms/Utils/SimplifyCFG.cpp

1644–1645

This change was made by inspection. I'll try to come up with a test case.

test/Assembler/token.ll

7

Right, I'll preclude this possibility.

test/Verifier/token1.ll

9

Sure, will do.

[majnemer]

test/Assembler/token.ll

7

Actually, it should be OK for a function to accept token parameters so long as it cannot return a token. If it returned a token, it would be ambiguous which token would be returned.

test/Verifier/token1.ll

9

I tried this and it didn't seem to work.

Running llvm-as over the following gave me a single error:

define void @test1(token %A, token %B) {
entry:
  br label %bb

bb:
  %phi = phi token [ %A, %bb ], [ %B, %entry]
; CHECK: PHI nodes cannot have token type!
  br label %bb
}

define void @test2(token %A, token %B) {
entry:
  br label %bb

bb:
  %sel = select i1 undef, token %A, token %B
; CHECK: select values cannot have token type
  br label %bb
}

define void @test3(token %A, token %B) {
entry: 
  alloca token 
; CHECK: invalid type for alloca 
  ret void 
}
@GV = external global token
; CHECK: invalid type for global variable

[JosephTremoulet]

test/Assembler/token.ll

7

The use case for return tokens that I can see is in the caller, to track a value back unobscurably to a callsite (which would require the call to be rewritten before/at lowering, so seems more likely with intrinsics than real functions).

The use case for parameter tokens I don't really understand. I think you're suggesting that it would be to introduce unobscurable interprocedural dataflow? Allowing that with multiple callers seems tantamount to allowing token PHIs.

At any rate, all of this is a thought experiment for possible future uses as far as I'm concerned, so I have no issue with the code going in as-is.

[majnemer]

• Let functions return tokens

[sanjoy]

Couple of questions

• [obsolete -- I see you disallow the token* type] Can we load / store through a pointer of type token *, allocated on the heap, or created via inttoptr?
• Can we do this transform:

if (cond) {
  %t0 = call token @p()
  call @consume(token %t0)
} else {
  %t1 = call token @p()
  call @consume(token %t1)
}

TO

%t = call token (cond ? @p : @q)()
call @consume(token %t)

?

lib/Analysis/LoopInfo.cpp

211

Just to be clear -- this is only conservatively correct, right? IIUC, we should be able to clone token producing instructions as long as we do not introduce phis / selects.

[majnemer]

In D11861#220835, @sanjoy wrote:

Couple of questions

• [obsolete -- I see you disallow the token* type] Can we load / store through a pointer of type token *, allocated on the heap, or created via inttoptr?
• Can we do this transform:

if (cond) {
  %t0 = call token @p()
  call @consume(token %t0)
} else {
  %t1 = call token @p()
  call @consume(token %t1)
}

TO

%t = call token (cond ? @p : @q)()
call @consume(token %t)

?

I don't think such a transformation would be canonical because the call is now indirect. Nevertheless, this wouldn't have an effect on my use case. Which would you prefer?

lib/Analysis/LoopInfo.cpp

211

Correct.

[majnemer]

• Let functions return tokens
• Only allow intrinsics to return/pass tokens around

[majnemer]

Do we feel we have reached consensus (perhaps weak consensus) or is there something you'd like to see addressed?

[JosephTremoulet]

Nothing more for me.

[sanjoy]

Looks good to me too.

[vsk]

Hi David,

Could you add a small snippet to test/Bitcode/compatibility.ll?

Something like:

define token @llvm.some.intrinsic() {
; CHECK: define token @llvm.some.intrinsic()
entry:
  ret token undef
; CHECK: ret token undef
}

You can find the rationale for this here: http://llvm.org/docs/DeveloperPolicy.html#ir-backwards-compatibility

Otherwise, LGTM.

[JosephTremoulet]

I realized I do have an issue to raise as I was going to hook up LLILC to the new EH representation.

lib/IR/Verifier.cpp

2201

I think we'll need to allow token PHIs with undef, if we want to use this for EH pads and we still want code commoning in EH pads to be legal.

I.e., if we have something along the lines of

cleanup1:
  cleanuppad
  ; chunk of code
  cleanupret unwind label %next1
cleanup2:
  cleanuppad
  ; identical chunk of code
  cleanupret unwind label %next2

then it was my understanding that it was a key design point of the new EH representation that it would be legal (if unprofitable) to transform this to

cleanup1:
  cleanuppad
  br label %shared_chunk
tail1:
  cleanupret unwind label %next1
shared_chunk:
  %origin = phi i1 [ 0, %cleanup1 ], [ 1, %cleanup2 ]
  ; chunk of code
  br i1 %origin, label %tail1, label %tail2
cleanup2:
  cleanuppad
  br label %shared_chunk
tail2:
  cleanupret unwind label %next2

but if cleanuppad produces a token that cleanupret consumes:

cleanup1:
  %tok1 = cleanuppad
  ; chunk of code
  cleanupret token %tok1, unwind label %next1
cleanup2:
  %tok2 = cleanuppad
  ; identical chunk of code
  cleanupret token %tok2, unwind label %next2

then a blanket rule against token PHIs precludes the transformation (the token defs would no longer dominate the uses). On the other hand, if we allow PHI with undef (as such a transformation would naturally introduce for any SSA values live across the combined regions), we could create this:

cleanup1:
  %tok1 = cleanuppad
  br label %shared_chunk
tail1:
  cleanupret token %tok1_copy, unwind label %next1
shared_chunk:
  %origin = phi i1 [ 0, %cleanup1 ], [ 1, %cleanup2 ]
  %tok1_copy = phi token [ %tok1, %cleanup1 ], [ undef, %cleanup2 ]
  %tok2_copy = phi token [ undef, %cleanup1 ], [ %tok2, %cleanup2 ]
  ; chunk of code
  br i1 %origin, label %tail1, label %tail2
cleanup2:
  %tok2 = cleanuppad
  br label %shared_chunk
tail2:
  cleanupret token %tok2_copy, unwind label %next2

(on the EH side: if things have changed and we're ok with disallowing this transformation, that's fine with me but it puts cleanupcall on my critical path)

That said, there are different things that "PHI with undef" could mean:

1. allow a token PHI with only one non-undef incoming value ( %x = phi token [ %y, %1 ], [ undef, %2 ], [ undef, %3 ] )
2. allow a token PHI with only one distinct non-undef incoming value ( %x = phi token [ %y, %1 ], [ %y, %2 ], [ undef, %3 ] )
3. also allow directly recursive token PHIs ( %x = phi token [ %y, %1 ], [ %x, %2] , [ undef, %3] )
4. others?
5. allow a web of token PHIs so long as there's only one unique incoming value, discounting undef and other phis in the web

#2 seems like a reasonable starting place to me, though any of them would be good enough for my immediate intended purpose (which is to encode finalies with this construct per Reid's suggestion (http://article.gmane.org/gmane.comp.compilers.llvm.devel/85937) as a staging plan until we add cleanupcall).

[rjmccall]

Could you clarify what, exactly, it is about your personality routine that requires a single exit to correspond to a single entry? Is that on a runtime level or just on a backend-lowering level? I am having trouble imagining what on a runtime level would rely on sniffing the address of the return instruction from the cleanup routine, but I am also having trouble imagining what it is about lowering that justifies such an incredibly invasive change to IR. You're introducing a type of "value" that instantly becomes a massive exception to every single standard rule about values. You can't put them in memory, you can't put them in PHIs, you can't put them in selects, you can't propagate them into or out of functions, you can't clone an instruction that contains a use, and I'm sure there are a dozen other difficulties.

This seems like a wildly general attempt at a solution, but its restrictions will probably prevent it from being useful for anything other than your EH problem, and I am very concerned that you will eventually discover that it isn't even all that useful or important for your EH problem, leaving this as an unwanted fruit simply bit-rotting on the vine.

[majnemer]

Having support for #2 makes our job in WinEHPrepare not seriously harder, I'm OK with it. Do any of the other stakeholders see any issues?

I'm a little confused though. Won't the preparation logic color the shared region twice, causing it to be duplicated anyway? If this is just a stepping stone to cleanupcall and no other stakeholder needs it, could we strengthen the restriction later?

[majnemer]

In D11861#223510, @rjmccall wrote:

Could you clarify what, exactly, it is about your personality routine that requires a single exit to correspond to a single entry? Is that on a runtime level or just on a backend-lowering level? I am having trouble imagining what on a runtime level would rely on sniffing the address of the return instruction from the cleanup routine, but I am also having trouble imagining what it is about lowering that justifies such an incredibly invasive change to IR. You're introducing a type of "value" that instantly becomes a massive exception to every single standard rule about values. You can't put them in memory, you can't put them in PHIs, you can't put them in selects, you can't propagate them into or out of functions, you can't clone an instruction that contains a use, and I'm sure there are a dozen other difficulties.

There are already values which may not be PHI'd or stuck in selects: LabelTy, MetadataTy, FunctionTy
There are also values which may not be loaded or stores to in memory: opaque structures, MetadataTy, FunctionTy, LabelTy
There are also values which cannot be passed into or out of functions and instructions which may not be cloned.

This seems like a wildly general attempt at a solution, but its restrictions will probably prevent it from being useful for anything other than your EH problem, and I am very concerned that you will eventually discover that it isn't even all that useful or important for your EH problem, leaving this as an unwanted fruit simply bit-rotting on the vine.

It was, in fact, originally designed to handle a JIT deopt problem. I am merely reusing it for my EH purposes.

[majnemer]

• Let functions return tokens
• Only allow intrinsics to return/pass tokens around
• Address Vedant's review comments

[rjmccall]

In D11861#223512, @majnemer wrote:

In D11861#223510, @rjmccall wrote:

Could you clarify what, exactly, it is about your personality routine that requires a single exit to correspond to a single entry? Is that on a runtime level or just on a backend-lowering level? I am having trouble imagining what on a runtime level would rely on sniffing the address of the return instruction from the cleanup routine, but I am also having trouble imagining what it is about lowering that justifies such an incredibly invasive change to IR. You're introducing a type of "value" that instantly becomes a massive exception to every single standard rule about values. You can't put them in memory, you can't put them in PHIs, you can't put them in selects, you can't propagate them into or out of functions, you can't clone an instruction that contains a use, and I'm sure there are a dozen other difficulties.

There are already values which may not be PHI'd or stuck in selects: LabelTy, MetadataTy, FunctionTy
There are also values which may not be loaded or stores to in memory: opaque structures, MetadataTy, FunctionTy, LabelTy

There are no values of FunctionTy at all; I think that's true of opaque as well, but maybe you can make an undef. MetadataTy makes no pretense at all to being an ordinary value; metadata are legal in exactly two positions (operands of other metadata, and a special location on instructions). LabelTy is only legal in successor lists, and as far as I've ever been able to tell, there's not really any good reason for it exist, or indeed basic blocks to be Values at all; you could certainly implement blockaddress without that.

There are also values which cannot be passed into or out of functions

Beyond the above values?

and instructions which may not be cloned.

Not based on their uses, I don't think. In fact, I don't remember there being any instructions that can't be cloned at all — even indirectbr is only *dangerous* to clone, and only because it tends to cause catastrophic use-list scaling problems. The closest thing I can think of is that you can't move an indirectbr (or any of its blockaddress destinations) to a different function.

This seems like a wildly general attempt at a solution, but its restrictions will probably prevent it from being useful for anything other than your EH problem, and I am very concerned that you will eventually discover that it isn't even all that useful or important for your EH problem, leaving this as an unwanted fruit simply bit-rotting on the vine.

It was, in fact, originally designed to handle a JIT deopt problem. I am merely reusing it for my EH purposes.

This proposal is still under design; it's changed multiple times in this very thread. It's at least not obvious to me that it still satisfies everyone else's needs with these changes, because I don't understand anyone else's needs, because they seem to me to be very hand-wavey.

Anyway, I am not deeply objecting to the feature; I would just like to understand why you need it for EH.

[majnemer]

In D11861#223523, @rjmccall wrote:

In D11861#223512, @majnemer wrote:

In D11861#223510, @rjmccall wrote:

Could you clarify what, exactly, it is about your personality routine that requires a single exit to correspond to a single entry? Is that on a runtime level or just on a backend-lowering level? I am having trouble imagining what on a runtime level would rely on sniffing the address of the return instruction from the cleanup routine, but I am also having trouble imagining what it is about lowering that justifies such an incredibly invasive change to IR. You're introducing a type of "value" that instantly becomes a massive exception to every single standard rule about values. You can't put them in memory, you can't put them in PHIs, you can't put them in selects, you can't propagate them into or out of functions, you can't clone an instruction that contains a use, and I'm sure there are a dozen other difficulties.

There are already values which may not be PHI'd or stuck in selects: LabelTy, MetadataTy, FunctionTy
There are also values which may not be loaded or stores to in memory: opaque structures, MetadataTy, FunctionTy, LabelTy

There are no values of FunctionTy at all; I think that's true of opaque as well, but maybe you can make an undef.

opaque can be inside of aggregates, function types can have opaque as their return type.

MetadataTy makes no pretense at all to being an ordinary value; metadata are legal in exactly two positions (operands of other metadata, and a special location on instructions). LabelTy is only legal in successor lists, and as far as I've ever been able to tell, there's not really any good reason for it exist, or indeed basic blocks to be Values at all; you could certainly implement blockaddress without that.

LabelTy can actually be used in places outside of successor lists and blockaddress. However, things go badly if the BasicBlock referred to be the label becomes unreachable as we expect all the non-successor uses to be blockaddress.

There are also values which cannot be passed into or out of functions

Beyond the above values?

and instructions which may not be cloned.

Not based on their uses, I don't think. In fact, I don't remember there being any instructions that can't be cloned at all — even indirectbr is only *dangerous* to clone, and only because it tends to cause catastrophic use-list scaling problems. The closest thing I can think of is that you can't move an indirectbr (or any of its blockaddress destinations) to a different function.

The noduplicate function attribute imbues calls and invokes may not be cloned: http://llvm.org/docs/LangRef.html#function-attributes

This seems like a wildly general attempt at a solution, but its restrictions will probably prevent it from being useful for anything other than your EH problem, and I am very concerned that you will eventually discover that it isn't even all that useful or important for your EH problem, leaving this as an unwanted fruit simply bit-rotting on the vine.

It was, in fact, originally designed to handle a JIT deopt problem. I am merely reusing it for my EH purposes.

This proposal is still under design; it's changed multiple times in this very thread. It's at least not obvious to me that it still satisfies everyone else's needs with these changes, because I don't understand anyone else's needs, because they seem to me to be very hand-wavey.

Anyway, I am not deeply objecting to the feature; I would just like to understand why you need it for EH.

My cleanup is materialized as a funclet which, by definition, has a single entry point. My personality routine has a restriction which requires that a cleanup transfer control to a single, specific, successor. This restriction comes about by the format of the unwind information that my personality routine uses to control its behavior, the cleanup has no mechanism to communicate where it would like to go next. I am in trouble if I have a cleanuppad which can reach two cleanuprets with different successors. By having my cleanuppad produce a value which may not be obscured and consume it in my cleanupret, I know that I can disregard other cleanupret instructions which appear reachable in the CFG but are dynamically unreachable.

[majnemer]

In all fairness, token type doesn't preclude the possibility of a different solution for WinEH.
It might be less odious to encode the funclet property in the BasicBlocks themselves. For example, we could state that some BBs are part a funclet. Then we would only need to consider cleanuppad instructions which lead to cleanupret instructions in the same funclet (with a verifier rule that all such cleanupret instructions have the same successor).

[JosephTremoulet]

I'm a little confused though. Won't the preparation logic color the shared region twice, causing it to be duplicated anyway? If this is just a stepping stone to cleanupcall and no other stakeholder needs it, could we strengthen the restriction later?

Yes. I think that the phi restriction and the need to clone in EH prep are very closely related; if you start with a cannot-be-PHIed def at the handler's single entry and a cannot-be-obscured use of it at every exit from the handler, then I don't see any way that a transformation could introduce a side-entry to that handler, because doing so would break the dominance relation between the entry and one of the exits, requiring an illegal PHI.

Supposing I'm right about that, and supposing we ultimately want the stricter PHI restriction, then since Clang duplicates cleanups and so only generates single-entry handlers, and since ultimately LLILC wants to use cleanupcall and so only generate single-entry handlers, it follows that cloning in EH preparation is just a stepping stone to cleanupcall. If that's the case, I'd rather spend cycles on cleanupcall than cloning so we get to our ultimate destination faster and without subtle/difficult-to-reason-about stepping-stone constructs along the way.

So that brings us to the question: do we ultimately want the stricter PHI restriction? I think the argument in favor of the stricter restriction is that it is simpler. I think the argument in favor of the looser restriction is that it allows transformations and IR generators more freedom, while still preserving the essential property that a token use can unambiguously be resolved to a single token def by walking the SSA graph.

I actually don't know whether we want that freedom for the EH case or not (where by 'we' I mean 'the community'; for LLILC specifically, we ultimately want cleanupcall and don't need this freedom). It allows code commoming across handlers, but since EH prep will necessarily undo such commoning (now that we've given up on using the new representation on all targets and translating it to landingpads in Dwarf EH Prep) that will never be beneficial from a CQ perspective, merely beneficial in the sense that the authors of these (hypothetical?) code commoning transformations won't have to check whether there are crossing token liveranges and abort if so.
I know that it used to be a design goal that "EH preparation should not assume that each basic block lives in exactly one funclet" [1], but I don't know if that's changed. I think the stricter restriction precludes that goal.

[1]: http://article.gmane.org/gmane.comp.compilers.llvm.devel/85915

[rjmccall]

In D11861#223528, @majnemer wrote:

opaque can be inside of aggregates, function types can have opaque as their return type.

Okay, but the corresponding aggregate/function type isn't usable as an aggregate/function: you can't GEP into the aggregate, and you can't call the function. My point is that arbitrary code does not have to worry about these types existing.

LabelTy can actually be used in places outside of successor lists and blockaddress. However, things go badly if the BasicBlock referred to be the label becomes unreachable as we expect all the non-successor uses to be blockaddress.

So, to me, that sounds like you *can't* use LabelTy in other places, but we just haven't formalized that restriction and enforced it in the verifier.

Not based on their uses, I don't think. In fact, I don't remember there being any instructions that can't be cloned at all — even indirectbr is only *dangerous* to clone, and only because it tends to cause catastrophic use-list scaling problems. The closest thing I can think of is that you can't move an indirectbr (or any of its blockaddress destinations) to a different function.

The noduplicate function attribute imbues calls and invokes may not be cloned: http://llvm.org/docs/LangRef.html#function-attributes

Ah, interesting.

Anyway, I am not deeply objecting to the feature; I would just like to understand why you need it for EH.

My cleanup is materialized as a funclet which, by definition, has a single entry point. My personality routine has a restriction which requires that a cleanup transfer control to a single, specific, successor. This restriction comes about by the format of the unwind information that my personality routine uses to control its behavior, the cleanup has no mechanism to communicate where it would like to go next. I am in trouble if I have a cleanuppad which can reach two cleanuprets with different successors. By having my cleanuppad produce a value which may not be obscured and consume it in my cleanupret, I know that I can disregard other cleanupret instructions which appear reachable in the CFG but are dynamically unreachable.

What happens if the cleanupret becomes unreachable? Also, it doesn't sound like you really need a restriction that the token can't be used in multiple places: if someone cloned the cleanupret, you could make that work pretty easily by just creating multiple returns from your funclet.

Also, won't being able to use tokens as parameters and returns completely break your analysis? I mean, I can't imagine what sort of transformation would actually spontaneously extract a function like that, but if you were willing to rely on statements like that, you wouldn't need token types at all, because no plausible transformation is going to spontaneously insert intermediate SSA defs, either.

[majnemer]

In D11861#224015, @rjmccall wrote:

In D11861#223528, @majnemer wrote:

opaque can be inside of aggregates, function types can have opaque as their return type.

Okay, but the corresponding aggregate/function type isn't usable as an aggregate/function: you can't GEP into the aggregate, and you can't call the function. My point is that arbitrary code does not have to worry about these types existing.

The following has Value * which cannot be demoted, it passes the verifier:

%X = type opaque

declare %X @g()

declare %X @h()

declare void @i(%X)

define %X @f(i1 %A) {
entry:
  br i1 %A, label %bb1, label %bb2

bb1:                                              ; preds = %entry
  %V1 = call %X @h()
  br label %bb

bb2:                                              ; preds = %entry
  %V2 = call %X @g()
  br label %bb

bb:                                               ; preds = %bb2, %bb1
  %P = phi %X [ %V1, %bb1 ], [ %V2, %bb2 ]
  ret %X %P
}

LabelTy can actually be used in places outside of successor lists and blockaddress. However, things go badly if the BasicBlock referred to be the label becomes unreachable as we expect all the non-successor uses to be blockaddress.

So, to me, that sounds like you *can't* use LabelTy in other places, but we just haven't formalized that restriction and enforced it in the verifier.

That's a fair assessment.

Not based on their uses, I don't think. In fact, I don't remember there being any instructions that can't be cloned at all — even indirectbr is only *dangerous* to clone, and only because it tends to cause catastrophic use-list scaling problems. The closest thing I can think of is that you can't move an indirectbr (or any of its blockaddress destinations) to a different function.

The noduplicate function attribute imbues calls and invokes may not be cloned: http://llvm.org/docs/LangRef.html#function-attributes

Ah, interesting.

Anyway, I am not deeply objecting to the feature; I would just like to understand why you need it for EH.

My cleanup is materialized as a funclet which, by definition, has a single entry point. My personality routine has a restriction which requires that a cleanup transfer control to a single, specific, successor. This restriction comes about by the format of the unwind information that my personality routine uses to control its behavior, the cleanup has no mechanism to communicate where it would like to go next. I am in trouble if I have a cleanuppad which can reach two cleanuprets with different successors. By having my cleanuppad produce a value which may not be obscured and consume it in my cleanupret, I know that I can disregard other cleanupret instructions which appear reachable in the CFG but are dynamically unreachable.

What happens if the cleanupret becomes unreachable?

Then we are left with a cleanuppad whose Value * is unused and the cleanupret would be deleted. This should be fine.

Also, it doesn't sound like you really need a restriction that the token can't be used in multiple places: if someone cloned the cleanupret, you could make that work pretty easily by just creating multiple returns from your funclet.

I can have multiple returns from my funclet, they just all have to go to the same place.

A token value can be used in multiple places, the users can be cloned just fine. What cannot be cloned is the instruction which produces the value as any phi nodes would be problematic.

Also, won't being able to use tokens as parameters and returns completely break your analysis? I mean, I can't imagine what sort of transformation would actually spontaneously extract a function like that, but if you were willing to rely on statements like that, you wouldn't need token types at all, because no plausible transformation is going to spontaneously insert intermediate SSA defs, either.

I have a verifier rule against parameters or returns of token type except when inside of intrinsics. Intrinsics, for obvious reasons, will have to make their token semantics quite clear.

[rjmccall]

In D11861#224049, @majnemer wrote:

The following has Value * which cannot be demoted, it passes the verifier:

I assume it crashes all the backends, though. Still, interesting; do you know if that's intentional?

Anyway, I am not deeply objecting to the feature; I would just like to understand why you need it for EH.

My cleanup is materialized as a funclet which, by definition, has a single entry point. My personality routine has a restriction which requires that a cleanup transfer control to a single, specific, successor. This restriction comes about by the format of the unwind information that my personality routine uses to control its behavior, the cleanup has no mechanism to communicate where it would like to go next. I am in trouble if I have a cleanuppad which can reach two cleanuprets with different successors. By having my cleanuppad produce a value which may not be obscured and consume it in my cleanupret, I know that I can disregard other cleanupret instructions which appear reachable in the CFG but are dynamically unreachable.

What happens if the cleanupret becomes unreachable?

Then we are left with a cleanuppad whose Value * is unused and the cleanupret would be deleted. This should be fine.

Also, it doesn't sound like you really need a restriction that the token can't be used in multiple places: if someone cloned the cleanupret, you could make that work pretty easily by just creating multiple returns from your funclet.

I can have multiple returns from my funclet, they just all have to go to the same place.

A token value can be used in multiple places, the users can be cloned just fine. What cannot be cloned is the instruction which produces the value as any phi nodes would be problematic.

Okay. But cloning the instruction would be fine if you cloned all of the uses as well?

Also, won't being able to use tokens as parameters and returns completely break your analysis? I mean, I can't imagine what sort of transformation would actually spontaneously extract a function like that, but if you were willing to rely on statements like that, you wouldn't need token types at all, because no plausible transformation is going to spontaneously insert intermediate SSA defs, either.

I have a verifier rule against parameters or returns of token type except when inside of intrinsics. Intrinsics, for obvious reasons, will have to make their token semantics quite clear.

Makes sense.

Okay, I may have just have misunderstood some of the restrictions you were proposing. I have no further objections.

[majnemer]

In D11861#224058, @rjmccall wrote:

In D11861#224049, @majnemer wrote:

The following has Value * which cannot be demoted, it passes the verifier:

I assume it crashes all the backends, though.

Oh, for sure :)

Still, interesting; do you know if that's intentional?

No idea. Pointers to opaque make sense but we forbid loading them.
The only real use-case that I can imagine is for special, magick, intrinsics.

Anyway, I am not deeply objecting to the feature; I would just like to understand why you need it for EH.

My cleanup is materialized as a funclet which, by definition, has a single entry point. My personality routine has a restriction which requires that a cleanup transfer control to a single, specific, successor. This restriction comes about by the format of the unwind information that my personality routine uses to control its behavior, the cleanup has no mechanism to communicate where it would like to go next. I am in trouble if I have a cleanuppad which can reach two cleanuprets with different successors. By having my cleanuppad produce a value which may not be obscured and consume it in my cleanupret, I know that I can disregard other cleanupret instructions which appear reachable in the CFG but are dynamically unreachable.

What happens if the cleanupret becomes unreachable?

Then we are left with a cleanuppad whose Value * is unused and the cleanupret would be deleted. This should be fine.

Also, it doesn't sound like you really need a restriction that the token can't be used in multiple places: if someone cloned the cleanupret, you could make that work pretty easily by just creating multiple returns from your funclet.

I can have multiple returns from my funclet, they just all have to go to the same place.

A token value can be used in multiple places, the users can be cloned just fine. What cannot be cloned is the instruction which produces the value as any phi nodes would be problematic.

Okay. But cloning the instruction would be fine if you cloned all of the uses as well?

Yes, it is totally fine to clone a BasicBlock wholesale where the token producer feeds into the user.

Also, won't being able to use tokens as parameters and returns completely break your analysis? I mean, I can't imagine what sort of transformation would actually spontaneously extract a function like that, but if you were willing to rely on statements like that, you wouldn't need token types at all, because no plausible transformation is going to spontaneously insert intermediate SSA defs, either.

I have a verifier rule against parameters or returns of token type except when inside of intrinsics. Intrinsics, for obvious reasons, will have to make their token semantics quite clear.

Makes sense.

Okay, I may have just have misunderstood some of the restrictions you were proposing. I have no further objections.

Great, thanks!

docs/LangRef.rst

 The label type represents code labels.
 
 :Syntax:
 
 ::
 
       label
 
+.. _t_token:
+
+Token Type
+^^^^^^^^^^
+
+:Overview:
+
+The token type is used when a value is associated with an instruction
+but all uses of the value must not attempt to introspect or obscure it.
+As such, it is not appropriate to have a :ref:`phi <i_phi>` or
+:ref:`select <i_select>` of type token.
+
+:Syntax:
+
+::
+
+      token
+
+
+
 .. _t_metadata:
 
 Metadata Type
 ^^^^^^^^^^^^^
 
 :Overview:
 
 The metadata type represents embedded metadata. No derived types may be

include/llvm-c/Core.h

typedef enum {
   LLVMLabelTypeKind,       /**< Labels */
   LLVMIntegerTypeKind,     /**< Arbitrary bit width integers */
   LLVMFunctionTypeKind,    /**< Functions */
   LLVMStructTypeKind,      /**< Structures */
   LLVMArrayTypeKind,       /**< Arrays */
   LLVMPointerTypeKind,     /**< Pointers */
   LLVMVectorTypeKind,      /**< SIMD 'packed' format, or other vector type */
   LLVMMetadataTypeKind,    /**< Metadata */
-  LLVMX86_MMXTypeKind      /**< X86 MMX */
+  LLVMX86_MMXTypeKind,     /**< X86 MMX */
+  LLVMTokenTypeKind        /**< Tokens */
 } LLVMTypeKind;
 
 typedef enum {
   LLVMExternalLinkage,    /**< Externally visible function */
   LLVMAvailableExternallyLinkage,
   LLVMLinkOnceAnyLinkage, /**< Keep one copy of function when linking (inline)*/
   LLVMLinkOnceODRLinkage, /**< Same, but only replaced by something
                             equivalent. */

include/llvm/Bitcode/LLVMBitCodes.h

enum TypeCodes {
     TYPE_CODE_METADATA = 16,    // METADATA
 
     TYPE_CODE_X86_MMX = 17,     // X86 MMX
 
     TYPE_CODE_STRUCT_ANON = 18, // STRUCT_ANON: [ispacked, eltty x N]
     TYPE_CODE_STRUCT_NAME = 19, // STRUCT_NAME: [strchr x N]
     TYPE_CODE_STRUCT_NAMED = 20,// STRUCT_NAMED: [ispacked, eltty x N]
 
-    TYPE_CODE_FUNCTION = 21     // FUNCTION: [vararg, retty, paramty x N]
+    TYPE_CODE_FUNCTION = 21,    // FUNCTION: [vararg, retty, paramty x N]
+
+    TYPE_CODE_TOKEN = 22        // TOKEN
   };
 
   // The type symbol table only has one code (TST_ENTRY_CODE).
   enum TypeSymtabCodes {
     TST_CODE_ENTRY = 1     // TST_ENTRY: [typeid, namechar x N]
   };
 
   // The value symbol table only has one code (VST_ENTRY_CODE).

include/llvm/IR/Type.h

enum TypeID {
     FloatTyID,       ///<  2: 32-bit floating point type
     DoubleTyID,      ///<  3: 64-bit floating point type
     X86_FP80TyID,    ///<  4: 80-bit floating point type (X87)
     FP128TyID,       ///<  5: 128-bit floating point type (112-bit mantissa)
     PPC_FP128TyID,   ///<  6: 128-bit floating point type (two 64-bits, PowerPC)
     LabelTyID,       ///<  7: Labels
     MetadataTyID,    ///<  8: Metadata
     X86_MMXTyID,     ///<  9: MMX vectors (64 bits, X86 specific)
+    TokenTyID,       ///< 10: Tokens
 
     // Derived types... see DerivedTypes.h file.
     // Make sure FirstDerivedTyID stays up to date!
-    IntegerTyID,     ///< 10: Arbitrary bit width integers
-    FunctionTyID,    ///< 11: Functions
-    StructTyID,      ///< 12: Structures
-    ArrayTyID,       ///< 13: Arrays
-    PointerTyID,     ///< 14: Pointers
-    VectorTyID       ///< 15: SIMD 'packed' format, or other vector type
+    IntegerTyID,     ///< 11: Arbitrary bit width integers
+    FunctionTyID,    ///< 12: Functions
+    StructTyID,      ///< 13: Structures
+    ArrayTyID,       ///< 14: Arrays
+    PointerTyID,     ///< 15: Pointers
+    VectorTyID       ///< 16: SIMD 'packed' format, or other vector type
   };
 
 private:
   /// Context - This refers to the LLVMContext in which this type was uniqued.
   LLVMContext &Context;
 
   TypeID   ID : 8;            // The current base type of this type.
   unsigned SubclassData : 24; // Space for subclasses to store data.
public:
   bool isFPOrFPVectorTy() const { return getScalarType()->isFloatingPointTy(); }
  
   /// isLabelTy - Return true if this is 'label'.
   bool isLabelTy() const { return getTypeID() == LabelTyID; }
 
   /// isMetadataTy - Return true if this is 'metadata'.
   bool isMetadataTy() const { return getTypeID() == MetadataTyID; }
 
+  /// isTokenTy - Return true if this is 'token'.
+  bool isTokenTy() const { return getTypeID() == TokenTyID; }
+
   /// isIntegerTy - True if this is an instance of IntegerType.
   ///
   bool isIntegerTy() const { return getTypeID() == IntegerTyID; } 
 
   /// isIntegerTy - Return true if this is an IntegerType of the given width.
   bool isIntegerTy(unsigned Bitwidth) const;
 
   /// isIntOrIntVectorTy - Return true if this is an integer type or a vector of
public:
   static Type *getHalfTy(LLVMContext &C);
   static Type *getFloatTy(LLVMContext &C);
   static Type *getDoubleTy(LLVMContext &C);
   static Type *getMetadataTy(LLVMContext &C);
   static Type *getX86_FP80Ty(LLVMContext &C);
   static Type *getFP128Ty(LLVMContext &C);
   static Type *getPPC_FP128Ty(LLVMContext &C);
   static Type *getX86_MMXTy(LLVMContext &C);
+  static Type *getTokenTy(LLVMContext &C);
   static IntegerType *getIntNTy(LLVMContext &C, unsigned N);
   static IntegerType *getInt1Ty(LLVMContext &C);
   static IntegerType *getInt8Ty(LLVMContext &C);
   static IntegerType *getInt16Ty(LLVMContext &C);
   static IntegerType *getInt32Ty(LLVMContext &C);
   static IntegerType *getInt64Ty(LLVMContext &C);
   static IntegerType *getInt128Ty(LLVMContext &C);
   

lib/Analysis/CodeMetrics.cpp

for (BasicBlock::const_iterator II = BB->begin(), E = BB->end();
     if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) {
       if (!AI->isStaticAlloca())
         this->usesDynamicAlloca = true;
     }
 
     if (isa<ExtractElementInst>(II) || II->getType()->isVectorTy())
       ++NumVectorInsts;
 
+    if (II->getType()->isTokenTy())
+      notDuplicatable = true;
+
     if (const CallInst *CI = dyn_cast<CallInst>(II))
       if (CI->cannotDuplicate())
         notDuplicatable = true;
 
     if (const InvokeInst *InvI = dyn_cast<InvokeInst>(II))
       if (InvI->cannotDuplicate())
         notDuplicatable = true;
 

lib/Analysis/LoopInfo.cpp

 }
 
 /// isSafeToClone - Return true if the loop body is safe to clone in practice.
 /// Routines that reform the loop CFG and split edges often fail on indirectbr.
 bool Loop::isSafeToClone() const {
   // Return false if any loop blocks contain indirectbrs, or there are any calls
   // to noduplicate functions.
   for (Loop::block_iterator I = block_begin(), E = block_end(); I != E; ++I) {
+    if ((*I)->getType()->isTokenTy())
+      return false;
+
     if (isa<IndirectBrInst>((*I)->getTerminator()))
       return false;
 
     if (const InvokeInst *II = dyn_cast<InvokeInst>((*I)->getTerminator()))
       if (II->cannotDuplicate())
         return false;
 
     for (BasicBlock::iterator BI = (*I)->begin(), BE = (*I)->end(); BI != BE; ++BI) {

lib/AsmParser/LLLexer.cpp

#define TYPEKEYWORD(STR, LLVMTY)                                               \
   TYPEKEYWORD("float",     Type::getFloatTy(Context));
   TYPEKEYWORD("double",    Type::getDoubleTy(Context));
   TYPEKEYWORD("x86_fp80",  Type::getX86_FP80Ty(Context));
   TYPEKEYWORD("fp128",     Type::getFP128Ty(Context));
   TYPEKEYWORD("ppc_fp128", Type::getPPC_FP128Ty(Context));
   TYPEKEYWORD("label",     Type::getLabelTy(Context));
   TYPEKEYWORD("metadata",  Type::getMetadataTy(Context));
   TYPEKEYWORD("x86_mmx",   Type::getX86_MMXTy(Context));
+  TYPEKEYWORD("token",     Type::getTokenTy(Context));
 #undef TYPEKEYWORD
 
   // Keywords for instructions.
 #define INSTKEYWORD(STR, Enum)                                                 \
   do {                                                                         \
     if (Keyword == #STR) {                                                     \
       UIntVal = Instruction::Enum;                                             \
       return lltok::kw_##STR;                                                  \

lib/Bitcode/Reader/BitcodeReader.cpp

case bitc::TYPE_CODE_LABEL:     // LABEL
       ResultTy = Type::getLabelTy(Context);
       break;
     case bitc::TYPE_CODE_METADATA:  // METADATA
       ResultTy = Type::getMetadataTy(Context);
       break;
     case bitc::TYPE_CODE_X86_MMX:   // X86_MMX
       ResultTy = Type::getX86_MMXTy(Context);
       break;
+    case bitc::TYPE_CODE_TOKEN:     // TOKEN
+      ResultTy = Type::getTokenTy(Context);
+      break;
     case bitc::TYPE_CODE_INTEGER: { // INTEGER: [width]
       if (Record.size() < 1)
         return error("Invalid record");
 
       uint64_t NumBits = Record[0];
       if (NumBits < IntegerType::MIN_INT_BITS ||
           NumBits > IntegerType::MAX_INT_BITS)
         return error("Bitwidth for integer type out of range");

lib/Bitcode/Writer/BitcodeWriter.cpp

for (unsigned i = 0, e = TypeList.size(); i != e; ++i) {
     case Type::FloatTyID:     Code = bitc::TYPE_CODE_FLOAT;     break;
     case Type::DoubleTyID:    Code = bitc::TYPE_CODE_DOUBLE;    break;
     case Type::X86_FP80TyID:  Code = bitc::TYPE_CODE_X86_FP80;  break;
     case Type::FP128TyID:     Code = bitc::TYPE_CODE_FP128;     break;
     case Type::PPC_FP128TyID: Code = bitc::TYPE_CODE_PPC_FP128; break;
     case Type::LabelTyID:     Code = bitc::TYPE_CODE_LABEL;     break;
     case Type::MetadataTyID:  Code = bitc::TYPE_CODE_METADATA;  break;
     case Type::X86_MMXTyID:   Code = bitc::TYPE_CODE_X86_MMX;   break;
+    case Type::TokenTyID:     Code = bitc::TYPE_CODE_TOKEN;     break;
     case Type::IntegerTyID:
       // INTEGER: [width]
       Code = bitc::TYPE_CODE_INTEGER;
       TypeVals.push_back(cast<IntegerType>(T)->getBitWidth());
       break;
     case Type::PointerTyID: {
       PointerType *PTy = cast<PointerType>(T);
       // POINTER: [pointee type, address space]

lib/IR/AsmWriter.cpp

void TypePrinting::print(Type *Ty, raw_ostream &OS) {
   case Type::FloatTyID:     OS << "float"; return;
   case Type::DoubleTyID:    OS << "double"; return;
   case Type::X86_FP80TyID:  OS << "x86_fp80"; return;
   case Type::FP128TyID:     OS << "fp128"; return;
   case Type::PPC_FP128TyID: OS << "ppc_fp128"; return;
   case Type::LabelTyID:     OS << "label"; return;
   case Type::MetadataTyID:  OS << "metadata"; return;
   case Type::X86_MMXTyID:   OS << "x86_mmx"; return;
+  case Type::TokenTyID:     OS << "token"; return;
   case Type::IntegerTyID:
     OS << 'i' << cast<IntegerType>(Ty)->getBitWidth();
     return;
 
   case Type::FunctionTyID: {
     FunctionType *FTy = cast<FunctionType>(Ty);
     print(FTy->getReturnType(), OS);
     OS << " (";

lib/IR/Core.cpp

LLVMTypeKind LLVMGetTypeKind(LLVMTypeRef Ty) {
   case Type::ArrayTyID:
     return LLVMArrayTypeKind;
   case Type::PointerTyID:
     return LLVMPointerTypeKind;
   case Type::VectorTyID:
     return LLVMVectorTypeKind;
   case Type::X86_MMXTyID:
     return LLVMX86_MMXTypeKind;
+  case Type::TokenTyID:
+    return LLVMTokenTypeKind;
   }
   llvm_unreachable("Unhandled TypeID.");
 }
 
 LLVMBool LLVMTypeIsSized(LLVMTypeRef Ty)
 {
     return unwrap(Ty)->isSized();
 }
LLVMTypeRef LLVMFP128TypeInContext(LLVMContextRef C) {
   return (LLVMTypeRef) Type::getFP128Ty(*unwrap(C));
 }
 LLVMTypeRef LLVMPPCFP128TypeInContext(LLVMContextRef C) {
   return (LLVMTypeRef) Type::getPPC_FP128Ty(*unwrap(C));
 }
 LLVMTypeRef LLVMX86MMXTypeInContext(LLVMContextRef C) {
   return (LLVMTypeRef) Type::getX86_MMXTy(*unwrap(C));
 }
+LLVMTypeRef LLVMTokenTypeInContext(LLVMContextRef C) {
+  return (LLVMTypeRef) Type::getTokenTy(*unwrap(C));
+}
 
 LLVMTypeRef LLVMHalfType(void) {
   return LLVMHalfTypeInContext(LLVMGetGlobalContext());
 }
 LLVMTypeRef LLVMFloatType(void) {
   return LLVMFloatTypeInContext(LLVMGetGlobalContext());
 }
 LLVMTypeRef LLVMDoubleType(void) {

lib/IR/Instructions.cpp

 //                              SelectInst Class
 //===----------------------------------------------------------------------===//
 
 /// areInvalidOperands - Return a string if the specified operands are invalid
 /// for a select operation, otherwise return null.
 const char *SelectInst::areInvalidOperands(Value *Op0, Value *Op1, Value *Op2) {
   if (Op1->getType() != Op2->getType())
     return "both values to select must have same type";
-  
+  if (Op1->getType()->isTokenTy())
+    return "select values cannot have token type";
+
   if (VectorType *VT = dyn_cast<VectorType>(Op0->getType())) {
     // Vector select.
     if (VT->getElementType() != Type::getInt1Ty(Op0->getContext()))
       return "vector select condition element type must be i1";
     VectorType *ET = dyn_cast<VectorType>(Op1->getType());
     if (!ET)
       return "selected values for vector select must be vectors";
     if (ET->getNumElements() != VT->getNumElements())

lib/IR/LLVMContextImpl.h

#include "llvm/IR/Metadata.def"
   ConstantUniqueMap<ConstantExpr> ExprConstants;
 
   ConstantUniqueMap<InlineAsm> InlineAsms;
 
   ConstantInt *TheTrueVal;
   ConstantInt *TheFalseVal;
 
   // Basic type instances.
-  Type VoidTy, LabelTy, HalfTy, FloatTy, DoubleTy, MetadataTy;
+  Type VoidTy, LabelTy, HalfTy, FloatTy, DoubleTy, MetadataTy, TokenTy;
   Type X86_FP80Ty, FP128Ty, PPC_FP128Ty, X86_MMXTy;
   IntegerType Int1Ty, Int8Ty, Int16Ty, Int32Ty, Int64Ty, Int128Ty;
 
   
   /// TypeAllocator - All dynamically allocated types are allocated from this.
   /// They live forever until the context is torn down.
   BumpPtrAllocator TypeAllocator;
   

lib/IR/LLVMContextImpl.cpp

 LLVMContextImpl::LLVMContextImpl(LLVMContext &C)
   : TheTrueVal(nullptr), TheFalseVal(nullptr),
     VoidTy(C, Type::VoidTyID),
     LabelTy(C, Type::LabelTyID),
     HalfTy(C, Type::HalfTyID),
     FloatTy(C, Type::FloatTyID),
     DoubleTy(C, Type::DoubleTyID),
     MetadataTy(C, Type::MetadataTyID),
+    TokenTy(C, Type::TokenTyID),
     X86_FP80Ty(C, Type::X86_FP80TyID),
     FP128Ty(C, Type::FP128TyID),
     PPC_FP128Ty(C, Type::PPC_FP128TyID),
     X86_MMXTy(C, Type::X86_MMXTyID),
     Int1Ty(C, 1),
     Int8Ty(C, 8),
     Int16Ty(C, 16),
     Int32Ty(C, 32),

lib/IR/Type.cpp

Type *Type::getPrimitiveType(LLVMContext &C, TypeID IDNumber) {
   case FloatTyID     : return getFloatTy(C);
   case DoubleTyID    : return getDoubleTy(C);
   case X86_FP80TyID  : return getX86_FP80Ty(C);
   case FP128TyID     : return getFP128Ty(C);
   case PPC_FP128TyID : return getPPC_FP128Ty(C);
   case LabelTyID     : return getLabelTy(C);
   case MetadataTyID  : return getMetadataTy(C);
   case X86_MMXTyID   : return getX86_MMXTy(C);
+  case TokenTyID     : return getTokenTy(C);
   default:
     return nullptr;
   }
 }
 
 /// getScalarType - If this is a vector type, return the element type,
 /// otherwise return this.
 Type *Type::getScalarType() const {

 //===----------------------------------------------------------------------===//
 
 Type *Type::getVoidTy(LLVMContext &C) { return &C.pImpl->VoidTy; }
 Type *Type::getLabelTy(LLVMContext &C) { return &C.pImpl->LabelTy; }
 Type *Type::getHalfTy(LLVMContext &C) { return &C.pImpl->HalfTy; }
 Type *Type::getFloatTy(LLVMContext &C) { return &C.pImpl->FloatTy; }
 Type *Type::getDoubleTy(LLVMContext &C) { return &C.pImpl->DoubleTy; }
 Type *Type::getMetadataTy(LLVMContext &C) { return &C.pImpl->MetadataTy; }
+Type *Type::getTokenTy(LLVMContext &C) { return &C.pImpl->TokenTy; }
 Type *Type::getX86_FP80Ty(LLVMContext &C) { return &C.pImpl->X86_FP80Ty; }
 Type *Type::getFP128Ty(LLVMContext &C) { return &C.pImpl->FP128Ty; }
 Type *Type::getPPC_FP128Ty(LLVMContext &C) { return &C.pImpl->PPC_FP128Ty; }
 Type *Type::getX86_MMXTy(LLVMContext &C) { return &C.pImpl->X86_MMXTy; }
 
 IntegerType *Type::getInt1Ty(LLVMContext &C) { return &C.pImpl->Int1Ty; }
 IntegerType *Type::getInt8Ty(LLVMContext &C) { return &C.pImpl->Int8Ty; }
 IntegerType *Type::getInt16Ty(LLVMContext &C) { return &C.pImpl->Int16Ty; }

 FunctionType *FunctionType::get(Type *Result, bool isVarArg) {
   return get(Result, None, isVarArg);
 }
 
 /// isValidReturnType - Return true if the specified type is valid as a return
 /// type.
 bool FunctionType::isValidReturnType(Type *RetTy) {
   return !RetTy->isFunctionTy() && !RetTy->isLabelTy() &&
   !RetTy->isMetadataTy();
 }
 
 /// isValidArgumentType - Return true if the specified type is valid as an
 /// argument type.
 bool FunctionType::isValidArgumentType(Type *ArgTy) {
   return ArgTy->isFirstClassType();
 }
 
while (type) {
     type = va_arg(ap, llvm::Type*);
   }
   setBody(StructFields);
   va_end(ap);
 }
 
 bool StructType::isValidElementType(Type *ElemTy) {
   return !ElemTy->isVoidTy() && !ElemTy->isLabelTy() &&
-         !ElemTy->isMetadataTy() && !ElemTy->isFunctionTy();
+         !ElemTy->isMetadataTy() && !ElemTy->isFunctionTy() &&
+         !ElemTy->isTokenTy();
 }
 
 /// isLayoutIdentical - Return true if this is layout identical to the
 /// specified struct.
 bool StructType::isLayoutIdentical(StructType *Other) const {
   if (this == Other) return true;
   
   if (isPacked() != Other->isPacked() ||
ArrayType *ArrayType::get(Type *ElementType, uint64_t NumElements) {
 
   if (!Entry)
     Entry = new (pImpl->TypeAllocator) ArrayType(ElementType, NumElements);
   return Entry;
 }
 
 bool ArrayType::isValidElementType(Type *ElemTy) {
   return !ElemTy->isVoidTy() && !ElemTy->isLabelTy() &&
-         !ElemTy->isMetadataTy() && !ElemTy->isFunctionTy();
+         !ElemTy->isMetadataTy() && !ElemTy->isFunctionTy() &&
+         !ElemTy->isTokenTy();
 }
 
 //===----------------------------------------------------------------------===//
 //                          VectorType Implementation
 //===----------------------------------------------------------------------===//
 
 VectorType::VectorType(Type *ElType, unsigned NumEl)
   : SequentialType(VectorTyID, ElType) {

 }
 
 PointerType *Type::getPointerTo(unsigned addrs) const {
   return PointerType::get(const_cast<Type*>(this), addrs);
 }
 
 bool PointerType::isValidElementType(Type *ElemTy) {
   return !ElemTy->isVoidTy() && !ElemTy->isLabelTy() &&
-         !ElemTy->isMetadataTy();
+         !ElemTy->isMetadataTy() && !ElemTy->isTokenTy();
 }
 
 bool PointerType::isLoadableOrStorableType(Type *ElemTy) {
   return isValidElementType(ElemTy) && !ElemTy->isFunctionTy();
 }

lib/IR/Verifier.cpp

void Verifier::visitFunction(const Function &F) {
   unsigned i = 0;
   for (Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E;
        ++I, ++i) {
     Assert(I->getType() == FT->getParamType(i),
            "Argument value does not match function argument type!", I,
            FT->getParamType(i));
     Assert(I->getType()->isFirstClassType(),
            "Function arguments must have first-class types!", I);
-    if (!isLLVMdotName)
+    if (!isLLVMdotName) {
       Assert(!I->getType()->isMetadataTy(),
              "Function takes metadata but isn't an intrinsic", I, &F);
+      Assert(!I->getType()->isTokenTy(),
+             "Function takes token but isn't an intrinsic", I, &F);
+    }
   }
 
+  if (!isLLVMdotName)
+    Assert(!F.getReturnType()->isTokenTy(),
+           "Functions returns a token but isn't an intrinsic", &F);
+
   // Get the function metadata attachments.
   SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
   F.getAllMetadata(MDs);
   assert(F.hasMetadata() != MDs.empty() && "Bit out-of-sync");
   VerifyFunctionMetadata(MDs);
 
   if (F.isMaterializable()) {
     // Function has a body somewhere we can't see.
void Verifier::visitPHINode(PHINode &PN) {
   // Ensure that the PHI nodes are all grouped together at the top of the block.
   // This can be tested by checking whether the instruction before this is
   // either nonexistent (because this is begin()) or is a PHI node.  If not,
   // then there is some other instruction before a PHI.
   Assert(&PN == &PN.getParent()->front() ||
              isa<PHINode>(--BasicBlock::iterator(&PN)),
          "PHI nodes not grouped at top of basic block!", &PN, PN.getParent());
 
+  // Check that a PHI doesn't yield a Token.
+  Assert(!PN.getType()->isTokenTy(), "PHI nodes cannot have token type!");
+
   // Check that all of the values of the PHI node have the same type as the
   // result, and that the incoming blocks are really basic blocks.
   for (Value *IncValue : PN.incoming_values()) {
     Assert(PN.getType() == IncValue->getType(),
            "PHI node operands are not the same type as the result!", &PN);
   }
 
   // All other PHI node constraints are checked in the visitBasicBlock method.
for (unsigned Idx = 1 + FTy->getNumParams(); Idx <= CS.arg_size(); ++Idx) {
       if (Attrs.hasAttribute(Idx, Attribute::InAlloca))
         Assert(Idx == CS.arg_size(), "inalloca isn't on the last argument!", I);
     }
   }
 
   // Verify that there's no metadata unless it's a direct call to an intrinsic.
   if (CS.getCalledFunction() == nullptr ||
       !CS.getCalledFunction()->getName().startswith("llvm.")) {
-    for (FunctionType::param_iterator PI = FTy->param_begin(),
-           PE = FTy->param_end(); PI != PE; ++PI)
-      Assert(!(*PI)->isMetadataTy(),
+    for (Type *ParamTy : FTy->params()) {
+      Assert(!ParamTy->isMetadataTy(),
              "Function has metadata parameter but isn't an intrinsic", I);
+      Assert(!ParamTy->isTokenTy(),
+             "Function has token parameter but isn't an intrinsic", I);
+    }
   }
 
+  // Verify that indirect calls don't return tokens.
+  if (CS.getCalledFunction() == nullptr)
+    Assert(!FTy->getReturnType()->isTokenTy(),
+           "Return type cannot be token for indirect call!");
+
   if (Function *F = CS.getCalledFunction())
     if (Intrinsic::ID ID = (Intrinsic::ID)F->getIntrinsicID())
       visitIntrinsicCallSite(ID, CS);
 
   visitInstruction(*I);
 }
 
 /// Two types are "congruent" if they are identical, or if they are both pointer

lib/Target/CppBackend/CPPBackend.cpp

#undef HANDLE_ATTR
     out(); nl(Out);
     Out << '}'; nl(Out);
   }
 }
 
 void CppWriter::printType(Type* Ty) {
   // We don't print definitions for primitive types
   if (Ty->isFloatingPointTy() || Ty->isX86_MMXTy() || Ty->isIntegerTy() ||
-      Ty->isLabelTy() || Ty->isMetadataTy() || Ty->isVoidTy())
+      Ty->isLabelTy() || Ty->isMetadataTy() || Ty->isVoidTy() ||
+      Ty->isTokenTy())
     return;
 
   // If we already defined this type, we don't need to define it again.
   if (DefinedTypes.find(Ty) != DefinedTypes.end())
     return;
 
   // Everything below needs the name for the type so get it now.
   std::string typeName(getCppName(Ty));

lib/Transforms/IPO/MergeFunctions.cpp

int FunctionComparator::cmpTypes(Type *TyL, Type *TyR) const {
   case Type::VoidTyID:
   case Type::FloatTyID:
   case Type::DoubleTyID:
   case Type::X86_FP80TyID:
   case Type::FP128TyID:
   case Type::PPC_FP128TyID:
   case Type::LabelTyID:
   case Type::MetadataTyID:
+  case Type::TokenTyID:
     return 0;
 
   case Type::PointerTyID: {
     assert(PTyL && PTyR && "Both types must be pointers here.");
     return cmpNumbers(PTyL->getAddressSpace(), PTyR->getAddressSpace());
   }
 
   case Type::StructTyID: {

lib/Transforms/Scalar/JumpThreading.cpp

for (; !isa<TerminatorInst>(I); ++I) {
 
     // Debugger intrinsics don't incur code size.
     if (isa<DbgInfoIntrinsic>(I)) continue;
 
     // If this is a pointer->pointer bitcast, it is free.
     if (isa<BitCastInst>(I) && I->getType()->isPointerTy())
       continue;
 
+    // Bail out if this instruction gives back a token type, it is not possible
+    // to duplicate it.
+    if (I->getType()->isTokenTy())
+      return ~0U;
+
     // All other instructions count for at least one unit.
     ++Size;
 
     // Calls are more expensive.  If they are non-intrinsic calls, we model them
     // as having cost of 4.  If they are a non-vector intrinsic, we model them
     // as having cost of 2 total, and if they are a vector intrinsic, we model
     // them as having cost 1.
     if (const CallInst *CI = dyn_cast<CallInst>(I)) {

lib/Transforms/Utils/InlineFunction.cpp

if (I->isEHPad()) {
         if (TPI->unwindsToCaller()) {
           SmallVector<Value *, 3> TerminatePadArgs;
           for (Value *Operand : TPI->operands())
             TerminatePadArgs.push_back(Operand);
           TerminatePadInst::Create(TPI->getContext(), UnwindDest, TPI);
           TPI->eraseFromParent();
           UpdatePHINodes(BB);
         }
-      } else if (auto *CPI = dyn_cast<CleanupPadInst>(I)) {
-        if (CPI->getNumOperands() == 0) {
-          CleanupPadInst::Create(CPI->getType(), {UnwindDest}, CPI->getName(),
-                                 CPI);
-          CPI->eraseFromParent();
-        }
       } else {
-        assert(isa<CatchPadInst>(I));
+        assert(isa<CatchPadInst>(I) || isa<CleanupPadInst>(I));
       }
     }
 
     if (auto *CRI = dyn_cast<CleanupReturnInst>(BB->getTerminator())) {
       if (CRI->unwindsToCaller()) {
         CleanupReturnInst::Create(CRI->getContext(), CRI->getReturnValue(),
                                   UnwindDest, CRI);
         CRI->eraseFromParent();

lib/Transforms/Utils/SimplifyCFG.cpp

static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB,
   }
 
   ++NumSpeculations;
   return true;
 }
 
 /// \returns True if this block contains a CallInst with the NoDuplicate
 /// attribute.
-static bool HasNoDuplicateCall(const BasicBlock *BB) {
+static bool BlockCannotBeDuplicated(const BasicBlock *BB) {
   for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
+    if (I->getType()->isTokenTy())
+      return true;
+
     const CallInst *CI = dyn_cast<CallInst>(I);
     if (!CI)
       continue;
     if (CI->cannotDuplicate())
       return true;
   }
   return false;
 }
static bool FoldCondBranchOnPHI(BranchInst *BI, const DataLayout &DL) {
   if (PN->getNumIncomingValues() == 1) {
     FoldSingleEntryPHINodes(PN->getParent());
     return true;
   }
 
   // Now we know that this block has multiple preds and two succs.
   if (!BlockIsSimpleEnoughToThreadThrough(BB)) return false;
 
-  if (HasNoDuplicateCall(BB)) return false;
+  if (BlockCannotBeDuplicated(BB)) return false;
 
   // Okay, this is a simple enough basic block.  See if any phi values are
   // constants.
   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
     ConstantInt *CB = dyn_cast<ConstantInt>(PN->getIncomingValue(i));
     if (!CB || !CB->getType()->isIntegerTy(1)) continue;
 
     // Okay, we now know that all edges from PredBB should be revectored to

test/Assembler/token.ll

+; RUN: llvm-as < %s | llvm-dis | FileCheck %s
+; RUN: verify-uselistorder %s
+; Basic smoke test for token type.
+
+; CHECK: declare void @llvm.token.foobar(token)
+declare void @llvm.token.foobar(token)

test/Bitcode/compatibility.ll

 define void @misc.metadata() {
   call void @f1(), !srcloc !11
   call void @f1(), !srcloc !12
   call void @f1(), !srcloc !13
   call void @f1(), !srcloc !14
   ret void
 }
 
+declare void @llvm.tokenfoo(token)
+; CHECK: declare void @llvm.tokenfoo(token)
+
 ; CHECK: attributes #0 = { alignstack=4 }
 ; CHECK: attributes #1 = { alignstack=8 }
 ; CHECK: attributes #2 = { alwaysinline }
 ; CHECK: attributes #3 = { cold }
 ; CHECK: attributes #4 = { convergent }
 ; CHECK: attributes #5 = { inlinehint }
 ; CHECK: attributes #6 = { jumptable }
 ; CHECK: attributes #7 = { minsize }

test/Verifier/token1.ll

+; RUN: not llvm-as %s -o /dev/null 2>&1 | FileCheck %s
+
+define void @f(token %A, token %B) {
+entry:
+  br label %bb
+
+bb:
+  %phi = phi token [ %A, %bb ], [ %B, %entry]
+; CHECK: PHI nodes cannot have token type!
+  br label %bb
+}

test/Verifier/token2.ll

+; RUN: not llvm-as %s -o /dev/null 2>&1 | FileCheck %s
+
+define void @f(token %A, token %B) {
+entry:
+  br label %bb
+
+bb:
+  %sel = select i1 undef, token %A, token %B
+; CHECK: select values cannot have token type
+  br label %bb
+}

test/Verifier/token3.ll

+; RUN: not llvm-as %s -o /dev/null 2>&1 | FileCheck %s
+
+define void @f(token %A, token %B) {
+entry:
+  alloca token
+; CHECK: invalid type for alloca
+  ret void
+}

test/Verifier/token4.ll

+; RUN: not llvm-as %s -o /dev/null 2>&1 | FileCheck %s
+
+@GV = external global token
+; CHECK: invalid type for global variable

test/Verifier/token5.ll

+; RUN: not llvm-as %s -o /dev/null 2>&1 | FileCheck %s
+
+define void @f(token %A) {
+entry:
+  ret void
+}
+; CHECK: Function takes token but isn't an intrinsic

test/Verifier/token6.ll

+; RUN: not llvm-as %s -o /dev/null 2>&1 | FileCheck %s
+
+define token @f() {
+entry:
+  ret token undef
+}
+; CHECK: Functions returns a token but isn't an intrinsic

test/Verifier/token7.ll

+; RUN: not llvm-as %s -o /dev/null 2>&1 | FileCheck %s
+
+define void @f() {
+entry:
+  call token () undef ()
+  ret void
+}
+; CHECK: Return type cannot be token for indirect call!